旅游

树型dp
和没有上司的舞会如出一辙

如果当前点居住了，那么子节点肯定不能居住。
如果当前点没住，那么子节点可以住可以不住
设
dp[x][1/0]为以x为根的子树带的最长时间，1表示住在x过，0表示没有
那么易得
dp[x][1]=1+Σ(dp[son][0])
dp[x][0]=Σmax(dp[son][0],dp[son][1])
最后答案就是dp[s][1]
因为指定了第一天一定要住在s

#include<bits/stdc++.h>
using namespace std;
vector<int> e[1<<20];
int dp[1<<20][2];
void dfs(int x,int f){
    dp[x][1]=1,dp[x][0]=0;
    for(auto son:e[x]){
        if(son==f) continue;
        dfs(son,x);
        dp[x][1]+=dp[son][0];
        dp[x][0]+=max(dp[son][0],dp[son][1]);
    }
}
int main(){
    ios::sync_with_stdio(0);
    int n,s;cin>>n>>s;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(s,-1);
    cout<<dp[s][1];
    return 0;
}