Strategic game树形DP解法(Poj1463,Uva1292)

已经写过本题用二分图的做法，见这儿。
本题的图是一棵树，求最小点覆盖也可以用树形DP的做法。
定义状态f[0/1][u]表示以u为根的子树，u选取/不选最少需要选取多少点来覆盖。
显然 f[0][u] = Sigma{f[1][v]},f[1][u] = Sigma{min(f[0][v],f[1][v])}+1 ( < u,v > 属于G且v!=u.father)

#include
#include
#include
using namespace std;

const int MAXN=2000+5;
int hd[MAXN],outd[MAXN];
int n,cnt;
struct Edge
{
	int t,n;
}e[MAXN<<1];
int f[2][MAXN];

inline void build(int f,int t)
{
	e[++cnt]=(Edge){t,hd[f]};
	hd[f]=cnt;
	++outd[f];
}

void dfs(int u,int fa)
{
	for(int i=hd[u];i;i=e[i].n)
	{
		int v=e[i].t;
		if(v==fa)
			continue;
		dfs(v,u);
		f[0][u]+=f[1][v];
		f[1][u]+=min(f[1][v],f[0][v]);
	}
	++f[1][u];
}

int main()
{
	while(~scanf("%d",&n))
	{
		cnt=0;
		memset(hd,0,sizeof hd);
		memset(e,0,sizeof e);
		memset(f,0,sizeof f);
		memset(outd,0,sizeof outd);
		int to,from,m;
		for(int i=0;i