树形dp旅游

链接：https://ac.nowcoder.com/acm/contest/87/G
来源：牛客网

Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。

旅行地图上有n个城市，它们之间通过n-1条道路联通。

Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。

他们不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。

XHRlyb想知道她与Cwbc最多能度过多少天的时光呢？

聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！

输入描述:

第一行，两个正整数n和s，表示城市个数和第一天住宿的城市s。
接下来n-1行，每行两个整数x和y，表示城市x与城市y之间有一条双向道路。

输出描述:

第一行，一个非负整数表示答案。

示例1

输入

复制

输出

复制

说明

第一天，在1号城市住宿，游览了1、2号城市。
第二天，在3号城市住宿，游览了4号城市，旅行结束。

备注:

1 ≤ n ≤ 500000, 1 ≤ s, x, y ≤ n。

这是个树形dp的题：
dp[i][1]表示选i节点住宿能够待的最长时间
dp[i][0]表示不选i节点住宿
如果选了i节点那么他的子节点一定不能选择住宿
所以

dp[i][1]+=dp[j][0]

如果不选择i节点住宿
那么i的子节点我们可以选择住或者不住，但因为我们要求时间最长，所以要取max

dp[i][0]+=max(dp[j][1],dp[j][0])

因为一旦选择i节点住宿后，时间一定会加一天，所以

dp[i][1]=1

#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;
int n,s;
/*
第一天会在s市住宿，并游览与它距离不超过1的所有城市，
之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。
他们不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。
XHRlyb想知道她与Cwbc最多能度过多少天的时光呢？
*/
const int maxn=1e6+100;
struct node{
    int next;
    int e;
}e[maxn];
int head[maxn];
int cnt;
void add(int u,int v){
    e[cnt].e=v;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
int f[maxn][2];
void dfs(int u,int fa){
    f[u][1]=1;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].e;
        if(fa==v){
            continue;
        }
        dfs(v,u);
        f[u][1]+=f[v][0];
        f[u][0]+=max(f[v][1],f[v][0]);
    }
}
int main(){
    memset(head,-1,sizeof(head));
    cin>>n>>s;
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    } 
    dfs(s,-1);
    cout<<f[s][1]<<endl;
}