树形dp先分析一部分的树形结构怎样最优以及单点（放和不放）的情况

题目：旅游

住宿点可以是未被游览的任何一点
游玩天数=住宿天数
即求最多住宿天数
易知：住宿点不能同时是父亲和儿子 即最大独立集

最大独立集（没有上司的舞会）（来的人尽可能多）
最小点覆盖（放的点尽可能少）
最小支配集（放的点尽可能少）
最大独立集和最小支配集有些相反的意思
判断是哪种模型或推转移方程时，先分析一部分的树形结构怎样最优，再看单点（放和不放）的情况

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const M=5e5+7;
int const N=5e5+7;
ll const INF=0x3f3f3f3f3f;
int n,m,s;
struct node{
    int a,len,next;
}e[M<<1];
int head[N],cnt;
void add(int x,int y,int len){
    e[++cnt].a =y;
    e[cnt].len =len;
    e[cnt].next =head[x];
    head[x]=cnt;
}
int vis[N];
ll f[N][2];
void dfs(int s){
    f[s][1]=1;
    vis[s]=1;
    for(int i=head[s];i!=-1;i=e[i].next){
        if(vis[e[i].a]) continue;
        vis[e[i].a]=1;
        dfs(e[i].a);
        f[s][0]+=max(f[e[i].a][0],f[e[i].a][1]);
        f[s][1]+=f[e[i].a][0];
    }
}
int main(){
    cin >> n >> s;
    memset(head,-1,sizeof head);
    memset(e,-1,sizeof e);
    for(int i=1;i<=n-1;++i){
        int a,b;cin >> a >> b;
        add(a,b,0);add(b,a,0);
    }
    dfs(s);
    cout << f[s][1];
    return 0;
}