http://www.lydsy.com/JudgeOnline/problem.php?id=1596

题意

一棵树，每个点可以支配直接与它相邻的点，求最小支配集。

题解

经典题目0.0

f[i][0]：以i为根的子树中均被覆盖且草地i上无信号塔所需的最小塔数

f[i][1]：以i为根的子树中均被覆盖且草地i上有信号塔所需的最小塔数

f[i][2]：以i为根的子树中除i点以外其余点均被覆盖所需的最小塔数

 转移方法：

f[i][1]=Σ(min(f[i.son][0..2]))

f[i][2]=Σ(f[i.son][0])

令sum=Σ(min(f[i.son][0..1]))

f[i][0]=min(f[i.son][1]+sum-min(f[i.son][0..1]))

i为叶节点时，f[i][0]显然是不合法的，所以应设为无穷大。 

#include<cstring>
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;
const int N=100001,M=2*N;
int n,k,f[N][3],v[M],next[M],head[N];
 
void add(int x,int y)
{
    v[++k]=y;next[k]=head[x];head[x]=k;
}
 
void dfs(int x,int fa)
{
    int sum=0;
    f[x][1]=1;
    for(int i=head[x];i;i=next[i])
        if(v[i]!=fa)
        {
            dfs(v[i],x);
            f[x][1]+=min(f[v[i]][0],min(f[v[i]][1],f[v[i]][2]));
            f[x][2]+=f[v[i]][0];
            sum+=min(f[v[i]][0],f[v[i]][1]);
        }
    f[x][0]=N;
    if(x!=1&&!next[head[x]])    return;
    for(int i=head[x];i;i=next[i])
        if(v[i]!=fa)
            f[x][0]=min(f[x][0],f[v[i]][1]+sum-min(f[v[i]][0],f[v[i]][1]));
}
     
 
int main()
{
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    printf("%d\n",min(f[1][1],f[1][0]));
}