转移正确性求助

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

定义

f[rt][0/1/2]

表示以

rt

为根的子树，除了根节点其他节点都保证点亮，选择了根节点/选择了至少一个根节点的儿子/根节点未被点亮时最少要选择多少个节点。转移如下：

CPP

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 它过了，不知道怎么证伪。

玄关

讨论操作

回复

相关推荐

转移正确性求助