旅游

Problem:

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

Solution:

树上最大独立集问题.
n个城市,n-1条路,显然就是一棵树,第一天在s城市住宿,所以s就是树根,而题中说在一个城市住宿了,那么距离为1的城市就不能住了,
所以住了节点i,那么他的儿子节点就不能住了,而我们从叶子节点往上推,最终住了节点s的值就是答案
dp[i][j] = k , j == 1,选第i个点住宿时,最多过几天;j == 0,不选第i个点住宿的时候,最多过几天
u是v的父亲:
dp[u][0] += max(dp[v][0],dp[v][1]) u不住宿,那么v可以住宿或者不住宿,选最大的
dp[u][1] += dp[v][0] u住宿,那么v一定不能住宿

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef long long ll;
const int maxn = 1e5 + 10;
int dp[maxn][2];
vector<int> G[maxn];
void dfs(int nowp,int fa){
    dp[nowp][1] = 1;
    _for(i,0,G[nowp].size()){
        int v = G[nowp][i];
        if(v == fa) continue;
        dfs(v,nowp);
        dp[nowp][1] += dp[v][0];
        dp[nowp][0] += max(dp[v][1],dp[v][0]);
    }
}
int main(){
    IOS;
    int n,s,x,y;
    cin>>n>>s;
    rep(i,2,n){
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(s,0);
    cout<<dp[s][1]<<endl;
    return 0;
}
/**
Problem:
Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。
旅行地图上有n个城市，它们之间通过n-1条道路联通。
Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。
他们不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。
XHRlyb想知道她与Cwbc最多能度过多少天的时光呢？
聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！ 

## Solution:
树上最大独立集问题.
    n个城市,n-1条路,显然就是一棵树,第一天在s城市住宿,所以s就是树根,而题中说在一个城市住宿了,那么距离为1的城市就不能住了,
    所以住了节点i,那么他的儿子节点就不能住了,而我们从叶子节点往上推,最终住了节点s的值就是答案
    dp[i][j] = k , j == 1,选第i个点住宿时,最多过几天;j == 0,不选第i个点住宿的时候,最多过几天 
    u是v的父亲:
        dp[u][0] += max(dp[v][0],dp[v][1]) u不住宿,那么v可以住宿或者不住宿,选最大的 
        dp[u][1] += dp[v][0] u住宿,那么v一定不能住宿 
*/