题解：P11018 Monochrome Tree

· · 题解

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. 首先显然有： $$ 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. 显然有: $$ 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. $$ dp_{x,cl[x]\land1,0} \gets dp_{x,cl[x],0}+1 $$ 因为 $x$ 没有被 1 操作覆盖，所以没有第二种转移。
  4. 因为 $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。