旅游

题意:有n个城市，它们之间通过n-1条道路联通。第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。最多能度过多少天?
题解:
分类讨论
表示在这个城市住下
表示不在这个城市住下
那么最后答案肯定是
然后如果我们要在第 个城市住下,那么 即第个城市住下,那么第个城市的子节点,全部不能入住
如果我们不在第个城市住下,那么
即,选取第个城市的子节点是否住下的最大值求和

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=5e5+5;
int n,s,f[N],g[N];vector<int>E[N];
void dfs(int u,int fa){
    f[u]=1;
    for(int v:E[u])
        if(v!=fa)
            dfs(v,u),f[u]+=g[v],g[u]+=max(f[v],g[v]);
}
int main(){
    scanf("%d%d",&n,&s);
    for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y),E[x].push_back(y),E[y].push_back(x);
    dfs(s,0);printf("%d\n",f[s]);return 0;
}