思路:

简单的思考一下,这题就是没有上司的舞会.首先,我假如选了这个点,那么它的子节点都不能选,假如我这个点选了的话,那么它的子节点既可以选,又可以不选.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int f[2][N];//当前这个点选不选的max.
vector<int>g[N];
int dfs(int u,int fa,bool op)
{
    if(f[op][u]!=-1)    return f[op][u];
    int res=0;if(op)    res++;
    if(op)
    {
        for(int v:g[u])
            if(v!=fa)    res+=dfs(v,u,false);
    }
    else
    {
        for(int v:g[u])
            if(v!=fa)    res+=max(dfs(v,u,true),dfs(v,u,false));
    }return f[op][u]=res;
}
int main()
{
    int n,s;//n个点,s为根.
    scanf("%d%d",&n,&s);
    memset(f,-1,sizeof f);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }printf("%d\n",dfs(s,s,true));
    return 0;
}