题解 | 旅游

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
typedef long long LL;

const int N=5e5+10;

int n, root;
vector<int> g[N];
int dp[N][2];  //dp[i][0/1]表示不在/在i这个城市住，其子树的合法最大值

void dfs(int u, int fa)
{
    for(int i=0; i<g[u].size(); i++){
        int j=g[u][i];
        if(j==fa) continue;
        dfs(j, u);
        dp[u][0]+=max(dp[j][0], dp[j][1]);
        dp[u][1]+=dp[j][0];
    }
}
int main()
{
    IOS
    cin>>n>>root;
    for(int i=1; i<=n; i++) dp[i][1]=1;
    int u, v;
    for(int i=0; i<n-1; i++){
        cin>>u>>v;
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(root, -1);
    cout<<dp[root][1];
    return 0;
}

题目翻译一下就是问一个树中，含根节点的 不相邻节点数量的最大值。

注意不要用链式前向星，数据量太大会爆内存！

然后不选该节点--子节点可以选也可以不选，是排斥或（离散数学胡言乱语）

选该节点，子节点只能不选

最后输出dp[root][1]，因为必须从root出发捏

#牛客春招刷题训练营#