[每日一题] [NC15748] 旅游

题目描述
Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。
旅行地图上有n个城市，它们之间通过n-1条道路联通。
Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。
他们不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。
XHRlyb想知道她与Cwbc最多能度过多少天的时光呢？
聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！

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

输出描述:
第一行，一个非负整数表示答案。

题解
树形dp，设dp[N][0]为不选此节点子树最大天数，dp[N][1]为选此节点子树最大天数
有dp转移方程

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

答案就是dp[s][1]
附代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 5e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

int dp[N][2];
vector<int>g[N];
void dfs(int x,int fa){
    for(int i:g[x]){
        if(i!=fa){
            dfs(i,x);
            dp[x][0]+=max(dp[i][1],dp[i][0]);
            dp[x][1]+=dp[i][0];
        }
    }
    dp[x][1]++;
}
void solve(){
    int n,s;cin>>n>>s;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        g[x].pb(y),g[y].pb(x);
    }
    dfs(s,0);
    cout<<dp[s][1];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}