题解 | 旅游

//这是一题树形dp，dp[cur][0]表示当前不选的最大值,dp[cur][1]表示当前选的最大值，最后dp[s][1]就是答案
#include <bits/stdc++.h>
using namespace std;
 
const int N = 5e5 + 10;
int dp[N][2];
vector<int> G[N];
 
void dfs(int cur, int pre){
    for(int i = 0; i < G[cur].size(); i++){ 
        int next = G[cur][i];
        if(next == pre)
            continue;
        dfs(next, cur);
        dp[cur][0] += max(dp[next][1],dp[next][0]); 
        dp[cur][1] += dp[next][0]; 
    }
}
 
int main(){
    int n, s;
    cin >> n >> s;
    for(int i = 1; i <= n; i++) 
        dp[i][1] = 1;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v); 
        G[v].push_back(u);
    }
    dfs(s, -1); 
    cout << dp[s][1] << endl;
    return 0;
}

#牛客春招刷题训练营#https://www.nowcoder.com/discuss/727521113110073344