[每一]树形DP，最大独立子集

https://ac.nowcoder.com/acm/problem/15748
最大独立子集：选出尽量多的点，使得任何两个节点均不相邻，输出一个最大独立集。

最大独立子集

f[i][0/1]表示以i为根时最大独立点的数量，f[][0]--不住 f[][1]--住
则 $f[u][1]$ 初始值为1， $f[u][1]+=\sum{}f[v][0];$
$f[u][0]+=\sum{}max(f[v][0],f[v][1])$ v是u的儿子节点

//AC @author:AROY
#include<bits/stdc++.h>
using namespace std;
#define N 100005
ll n, k[N];
ll ans, f[N][2];//f[][0]--不住 f[][1]--住
ll tot,rt,dis[N],p[N],h[N],ne[N<<1],u[N<<1],wi[N<<1];
void add(int u,int v){p[++tot]=v;ne[tot]=h[u];h[u]=tot;}
void dfs(int u,int fa){
    f[u][0]=0;f[u][1]=1;
    for(int i=h[u];i;i=ne[i])if(p[i]!=fa)
    {
        int v=p[i];
        dfs(p[i],u);
        f[u][1]+=f[v][0];
        f[u][0]+=max(f[v][0],f[v][1]);
    }
}
int main()
{
    int s;
    cin>>n>>s;
    for(int i=0;i<n;++i){
        int u,v;cin>>u>>v;
        add(u,v);add(v,u);
    }
    dfs(s,0);
    cout<<f[s][1];
}

最小点覆盖

对于图G=(V,E)来说，最小点覆盖指的是从V中取尽量少的点组成一个集合，使得E中所有的边都与取出来的点相连
TODO

最小支配集

指的是从V中取尽量少的点组成一个集合，使得对于V中剩余的点都与取出来的点有边相连。
dp[i][0]：表示点i属于支配集，并且以点i为根的子树都被覆盖了的情况下支配集中所包含的的最少点的个数。

dp[i][1]：i不属于支配集，且以i为根的子树都被覆盖，且i被其中不少于1个子节点覆盖的情况下支配集中所包含最少点的个数。

　dp[i][2]：i不属于支配集，且以i为根的子树都被覆盖，且i没被子节点覆盖的情况下支配集中所包含最少点的个数。

　　对于第一种状态，dp[i][0]等于每个儿子节点的3种状态（其儿子是否被覆盖没有关系）的最小值之和加1，即只要每个以i的儿子为根的子树都被覆盖，再加上当前点i,所需要的最少点的个数，方程如下：

　　 $dp[i][0]=1+Σmin(dp[u][0],dp[u][1],dp[u][2])(p[u]=i)$

void DP(int u,int p)
{
    dp[u][2]=0;
    dp[u][0]=1;
    bool s=false;
    int sum=0,inc=INF;
    int k;
    for(k=head[u];k!=-1;k=edge[k].next)
    {
        int to=edge[k].to;
        if(to==p)continue;
        DP(to,u);
        dp[u][0]+=min(dp[to][0],min(dp[u][1],dp[u][2]));
        if(dp[to][0]<=dp[to][1])
        {
            sum+=dp[to][0];
            s=true;
        }
        else
        {
            sum+=dp[to][1];
            inc=min(inc,dp[to][0]-dp[to][1]);
        }
        if(dp[to][1]!=INF&&dp[u][2]!=INF)dp[u][2]+=dp[to][1];
        else dp[u][2]=INF;
    }
    if(inc==INF&&!s)dp[u][1]=INF;
    else
    {
        dp[u][1]=sum;
        if(!s)dp[u][1]+=inc;
    }
}