旅游（树形dp）

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

假设有这么一棵树
如果：我们第一次在1住宿 然后 游览完 2 3 只需要一天的时间
但是如果： 我们不选1节点住宿， 我们选第一天2节点住宿然后游览完1
然后第二天选3节点住宿 ，这样时间比第一次长

题目要求的s（根节点）是一个确定的住宿节点
那么这样我们就可以考虑树上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

因为存图的时候是双向存图，父子边直接continue
代码

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const int maxn=5e5+7;
const ll mod = 1e9+7;
const int N =1e6+7;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
vector<ll>v[maxn];
ll n,s,dp[maxn][2];
void dfs(ll u,ll p) {
    dp[u][1]=1;
    for(int e:v[u]) {
        if(e==p) continue;
        dfs(e,u);
        dp[u][1]+=dp[e][0];
        dp[u][0]+=max(dp[e][0],dp[e][1]);
    }
}
int UpMing() {
    n=read();
    s=read();
    for(int i=1 ; i<=n-1 ; i++) {
        ll x=read();
        ll y=read();
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(s,-1);
    out(dp[s][1]);
    Accept;
}