BZOJ 1596 [Usaco2008 Jan]电话网络

题目大意

求一棵树的最小覆盖集。

树形DP傻题但是我还是弄错啦啊啊啊啊啊（无聊到朗读的同学注意一下是5个“啊”别念错谢谢）

设$f_{i,j}$表示i号点通电，它子树也通电的最小通电数量，$g_{i,j}$表示i号点不通电，它子树使它通电的最小通电数量，$h_{i,j}$表示i号点不通电，它子树也不通电的最小通电数，进行一番DP就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 10001
int to[N<<1],nxt[N<<1],head[N],tot;
long long f[N],g[N],h[N];
inline void AE(int X,int Y){to[++tot]=Y,nxt[tot]=head[X],head[X]=tot;}
void DFS(int pos,int pre)
{
	f[pos]=1,h[pos]=0x3f3f3f3f;
	long long tmp=0;
	for(int i=head[pos];i;i=nxt[i]) if(to[i]!=pre)
		DFS(to[i],pos),f[pos]+=min(min(f[to[i]],g[to[i]]),h[to[i]]),g[pos]+=h[to[i]],tmp+=min(f[to[i]],h[to[i]]);
	for(int i=head[pos];i;i=nxt[i]) if(to[i]!=pre)
		h[pos]=min(h[pos],f[to[i]]+tmp-min(f[to[i]],h[to[i]]));
}
int main()
{
	int n,X,Y;
	scanf("%d",&n);
	for(int i=2;i<=n;++i) scanf("%d%d",&X,&Y),AE(X,Y),AE(Y,X);
	DFS(1,0);
	printf("%lld\n",min(f[1],h[1]));
	return 0;
}