题解 | #xinjun与阴阳师#

思路

对于每个选择的点，其周围的点都是不能选的，我们从根结点出发深搜+DP，就能求出答案了。
可以参考 没有上司的舞会 ，这道题就是退化版。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
struct E{
    int to,next;
}edge[maxn<<1];

int n,s,cnt=0,dp[maxn][2];
int x,y,head[maxn],du[maxn];

void addedge(int from,int to){
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs(int node,int pre){
    for(int i=head[node];i;i=edge[i].next){
        int to=edge[i].to;
        if(to!=pre){
            dfs(to,node);
            dp[node][0]+=max(dp[to][1],dp[to][0]);
            dp[node][1]+=dp[to][0];
        }
    }
}

int main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        du[i]=0;
        dp[i][1]=1;
        dp[i][0]=0;
    }
    for(int i=1;i<n;i++){
        cin>>x>>y;
        addedge(x,y);
        addedge(y,x);
        du[x]++;du[y]++;
    }
    dfs(s,0);
    cout<<dp[s][1];
    return 0;
}