旅游

题意：
有一棵n个节点的树，第一天你在s点住宿，每一天你可以浏览与它距离不超过1的节点，你不能住宿在你已经浏览过的节点，求你最多住宿几天？

思路：
树状dp，以s节点为根。
dp[i][1/0]表示在i为根的子树中是否在i节点住宿的最大住宿次数。
如果u是父节点，v是子节点。
dp[u][1]= dp[v][0]+1;(v为u的子节点)
dp[u][0]= max(dp[v][1],dp[v][0]);(v为u的子节点)
答案为dp[s][1].

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1024523

using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

vector<int> g[500005];
int dp[500005][2];

void dfs(int v,int f)
{
    for(int i=0;i<g[v].size();i++)
    {
        if(g[v][i]==f)
        {
            continue;
        }
        dfs(g[v][i],v);
        dp[v][1]+=dp[g[v][i]][0];
        dp[v][0]+=max(dp[g[v][i]][1],dp[g[v][i]][0]);
    }
    dp[v][1]++;
}

int main()
{
    int n, s;
    scanf("%d%d",&n,&s);
    for(int i=0;i<n-1;i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(s,-1);
    cout << dp[s][1] << endl;
    return 0;
}