题目链接 P2899 [USACO08JAN] Cell Phone Network G

定义 $f[rt][0/1/2]$ 表示以 $rt$ 为根的子树，除了根节点其他节点都保证点亮，选择了根节点/选择了至少一个根节点的儿子/根节点未被点亮时最少要选择多少个节点。 转移如下：

void dfs(int rt,int fa)
{
	f[rt][0]=1;
	f[rt][1]=N;
	for(int i=Head[rt];i;i=E[i].nxt)
	{
		int son=E[i].to;
		if(son==fa)	
 	   		continue;
		dfs(son,rt);
		f[rt][0]+=min(min(f[son][0],f[son][1]),f[son][2]);
		f[rt][1]=min(f[rt][2]+f[son][0],f[rt][1]+min(f[son][0],f[son][1]));
		f[rt][2]+=f[son][1];
	}
}

答案取 $\max (f[1][0],f[1][1])$

个人感觉这个转移是错误的，因为可能会有 $f[rt][1]$ 全是 $f[son][1]$ 转移过来的情况，但这个 dfs 它过了，不知道怎么证伪。

玄关