旅游

树形DP

其实这道题大体思路跟牛客小白月赛25的C题差不多，或者说是大部分的树形DP可能都是这个思路吧。

首先在这道题中，一共有条边，很明显是棵树，接着看，它限制了每次游览只能游览当前住宿过的城市周围距离为1的所有城市，这不就是对于一个点去参观所有他的儿子节点吗？再然后，他会选择一个城市住宿，那么我们就有两种选择，1是在这个城市住，2是不住，去考虑其他的城市。

在节点上不住/住的子树上能呆的最长时间

对于不住的情况，那么对于儿子节点是有一次居住的机会的。
所以

对于要在点居住的情况，则儿子节点没有了居住的机会。
所以

又因为是要去参观所有的儿子节点，则：

因为住宿，时间会过去一天，所以

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=500000 + 5;
int n,s,f[MAX_N][2];
int Last[MAX_N],Next[MAX_N<<1],End[MAX_N<<1],tot;
void addedge(int x,int y){
    End[++tot]=y;
    Next[tot]=Last[x];
    Last[x]=tot;
}
void solve(int x,int fa){
    for(int i=Last[x];i;i=Next[i]){
        int y=End[i];
        if(y!=fa){
            solve(y,x);;
            f[x][1]+=f[y][0];
            f[x][0]+=max(f[y][0],f[y][1]);
        }
    }
    f[x][1]++;
}
int main(){
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    solve(s,0);
    printf("%d\n",f[s][1]);
    return 0;
}