旅游

题意：有一个n个城市有（n-1）条道路的无向图，有二人打算旅游，第一天住在s市，并浏览了周围距离不大于1的城市，每天会选择一个城市住，他们不想住在已经浏览过的城市，并且他们想旅游时间尽可能长.求最长旅游多少天？

思路：树状dp,dp[v][0/1]表示以v为根节点的树，根节点分是否住的的最大旅游天数。
dp[v][0]= (max(dp[k][0],dp[k][1]))(k是v的子节点);
dp[v][1]=( dp[k][0])+1 (k是v的子节点);
因为一个城市住则他的子节点不可能住，不住则子节点可住可不住。
代码：

#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;
}