自动搬运

查看原文

来自洛谷，原作者为

	arimaw 爆炸吧现充

搬运于2025-08-24 23:03:32，当前版本为作者最后更新于2024-08-31 22:06:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Monochrome Tree 题解

一眼树形dp。

首先考虑没有操作 1 的情况（即不用从根到某个节点的翻转操作）。

设 $dp_{x,0/1}$ 表示以 $x$ 为根的子树且子树中的节点颜色都为白/黑色的最少步数。记 $cl_x$ 表示 $x$ 号节点原本的颜色，那么有转移：

$$dp_{x,0}\gets\min(dp_{y,0},dp_{y,1}+1)$$ $$dp_{x,1}\gets\min(dp_{y,1},dp_{y,0}+1)$$

其中 $y$ 表示 $x$ 的儿子。 特别的，对于叶子节点有

$$dp_{x,cl[x]}=0,dp_{x,cl[x]\land1}=1$$

所以为什么不给这部分的部分分 QwQ 。

接下来我们考虑往其中加入 1 操作，我们发现对于一个节点，我们并不关心 1 操作具体用了几次，只关心使用 1 操作次数的奇偶性（奇数颜色反转，偶数颜色不变），而且 1 操作还具有传递性（可以从儿子传递到父亲），这启发我们考虑一个新的 $dp$ 状态。

设 $dp_{x,0/1,0/1}$ 表示以 $x$ 号节点为根的子树颜色为白 / 黑，且 $x$ 号节点被1操作覆盖了奇 / 偶数次（有 / 没有被覆盖）。

答案即为 $\min(dp_{1,1,0},dp_{1,1,1})$。

接下来我们考虑如何进行转移。

我们发现如果直接处理当前节点和儿子节点的转移并不是很好想（可能是因为我太菜了），由于最终所有儿子的颜色要一样，所以最后的状态并不多，所以我们可以先把儿子的状态合并好，再处理所有儿子到父亲的转移（详见代码）。

因为只是单纯的合并儿子，所以转移比较简单，我们有：

$$dp_{x,i,j\land k}\gets\min(dp_{x,i,j\land k},dp_{x,i,j}+dp_{y,i,k}) $$

在接下来的讨论中，我们记儿子的状态为 $f$，父亲的状态为 $dp$ 。

接下来我们考虑从儿子转移到父亲，总共有四种情况，所以我们进行分类讨论：

1. $x$ 的颜色不变，且 $x$ 没有被1操作覆盖。 首先显然有：

   $$dp_{x,cl[x],0} \gets f_{x,cl[x],0}$$

   但是由于我们可以在 $x$ 处单独进行一次 1 操作，所以还有：

   $$dp_{x,cl[x].0} \gets f_{x,cl[x],1}+1$$

2. $x$ 的颜色改变，且 $x$ 有被 1 操作覆盖 显然有:

   $$dp_{x,cl[x]\land1,1} \gets f_{x,cl[x]\land1,1}$$

   但是我们还是可以在 $x$ 处单独进行一次操作，所以有：

   $$dp_{x,cl[x]\land 1,1} \gets f_{x,cl[x]\land1,0}+1$$

3. $x$ 的颜色改变，且 $x$ 没有被 1 操作覆盖这种情况我们显然可以从情况 1 转移过来（在 $x$ 处进行一次操作），所以有：

   $$dp_{x,cl[x]\land1,0} \gets dp_{x,cl[x],0}+1$$

   因为 $x$ 没有被 1 操作覆盖，所以没有第二种转移。

4. $x$ 的颜色不变，且 $x$ 有被 1 操作覆盖 因为 $x$ 有被 1 操作覆盖颜色却没有改变，所以肯定在 $x$ 处进行了一次二操作，所以有：

   $$dp_{x,cl[x],1} \gets dp_{x,cl[x]\land1,1}+1$$

到这里就结束了，还有一些细节详见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10,inf=1e9+10;
vector<int> e[N];
int dp[N][2][2],f[N][2][2],cl[N],n;
// 开两个数组是怕转移时出现重复
void clean(int x){
	for(int i=0;i<2;++i) for(int j=0;j<2;++j) f[x][i][j]=inf;
}
void dfs(int x,int fa){
	int fla=0;
	for(int i=0;i<2;++i) for(int j=0;j<2;++j) dp[x][i][j]=inf;
	clean(x);
	for(int y:e[x]){
		if(y==fa) continue;
		dfs(y,x);
		fla++;
		clean(x);
		if(fla==1){
			for(int i=0;i<2;++i) 
			for(int j=0;j<2;++j) 
			f[x][i][j]=dp[y][i][j];
		}//第一个儿子直接赋值就好
		else {
			for(int i=0;i<2;++i) 
			for(int j=0;j<2;++j) 
			for(int k=0;k<2;++k){
		    	f[x][i][j^k]=min(f[x][i][j^k],dp[x][i][j]+dp[y][i][k]);//转移
     		}
		}
		for(int i=0;i<2;++i) for(int j=0;j<2;++j) dp[x][i][j]=f[x][i][j];//复制
	}
    for(int i=0;i<2;++i) for(int j=0;j<2;++j) dp[x][i][j]=inf;
	dp[x][cl[x]][0]=min(f[x][cl[x]][0],f[x][cl[x]][1]+1);
	dp[x][cl[x]^1][1]=min(f[x][cl[x]^1][0]+1,f[x][cl[x]^1][1]);
	dp[x][cl[x]^1][0]=min(dp[x][cl[x]^1][0],dp[x][cl[x]][0]+1);
	dp[x][cl[x]][1]=min(dp[x][cl[x]][1],dp[x][cl[x]^1][1]+1);
//对应题解中的1,2,3,4 注意后两个是dp而不是f
	if(fla==0){
		dp[x][cl[x]^1][0]=1;
		dp[x][cl[x]][0]=0;
		dp[x][cl[x]^1][1]=1;
	}//叶子节点赋初值
}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("E.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&cl[i]);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	printf("%d\n",min(dp[1][1][1],dp[1][1][0]));
	return 0;
}

第一次写题解有不好的地方请见谅 QwQ。