CF1879E Interactive Game with Coloring 题解

· · 题解

小蒟蒻觉得这道题非常的有意思，所以写一篇题解复盘一下思路。

因此这篇题解不会使用传统的“题解”格式，而是会更接近“解题报告”。

CF1879E 题解

题意简述

给定一棵 n 个节点的有根树，你需要对树的每条边进行染色。你要和交互库在这棵树上玩这样一个游戏：

交互库选择一个起点，放置棋子。

交互库不告诉你棋子的位置，但会告诉你和棋子所连的边的颜色情况（每种颜色的边有几条）。

你需要告诉交互库一种颜色，交互库会沿着这条颜色的边移动。如果这种颜色的边数大于 1，则由交互库来选择。

如果棋子向叶向走，那么交互库胜。走到根节点则你胜。

求出在保证获胜的情况下，最少需要染几种颜色。给出染色方案，并与交互库玩这个游戏。

思路引导

在本文中:

节点从 1 起标，且 1 是根节点；

节点层数从 0 起标，根节点是第 0 层；

边的层数定义为，其沿叶向连到的节点层数。

我们先来考虑怎么来染色。

首先，容易注意到，对于每一个节点，根向的边不能与叶向的边颜色相同。否则，你意图选择根向的边，但交互库可以选择颜色相同的叶向边走。

那么我们就可以把根向染成一种颜色，把叶向全部染成相同的另一种颜色。于是，我们就有了第一版思路：对于奇数层边，全部染成红色，对于偶数层边，全部染成蓝色。如图所示

这样对于每一个节点，我们选择只有一条边的颜色，就可以一直沿着根向走。

但我们也很快可以发现问题。如果一个节点只有一个儿子，也就是叶向边和根向边都只有一条（如下图实心点），那么我们选哪一条呢？

发现两种颜色是不够的。（虽然这个图用两种颜色染是可行的，但我们先沿着目前的策略，这个之后再讨论）

我们考虑用同样的思路，使用三种颜色进行染色。也就是同一层的边用一种颜色染，相邻层的边“红蓝绿”循环染，如下图所示。

这样，我们的策略就是：如果节点连的边是红蓝，那么选红；如果连的边是蓝绿，那么选蓝；如果连的边是红绿，那么选绿。可以证明这样的染色方案和策略是一定可行的。

也就是说，用 3 种颜色是一定可行的，但有可能不是颜色种类最少的。

那哪些情况用两种颜色就可以染好呢？

我们将“只有 1 个儿子的节点”称为“单子节点”。

如果树中不存在“单子节点”，那么用两种颜色就可以染好。

如果所有的“单子节点”深度的奇偶相同，也可以用两种颜色染好。游戏时我们规定，对于单子节点，我们沿着红色/蓝色走即可。如下图所示。

比如上图我们就规定单子节点沿红色边走。

其实再仔细想想，所谓“层数奇偶相同”的本质其实是，根向边的颜色相同。也就是对于一个图，如果我们有办法能让所有单子节点根向边的颜色相同，就可以用 2 种颜色完成染色。

所以我们接下来考虑，对于层数奇偶性不同的单子节点，怎么处理让它们根向边的颜色相同。

再回顾一下我们一开始的想法，之所以让同一层的边颜色相同，是为了让根向边不要和叶向边撞色。然而根节点没有根向边，所以我们可以让根节点连接的第 1 层边颜色不同。

我们将 1 的所有儿子为根的子树称为“大子树”

然后我们就会发现，奇偶性不同的单子节点，它们的根向边就可以相同了。对于奇数层的单子节点，我们正常处理；对于偶数层的单子节点，我们找到其所在的“大子树”的根，翻转子树根的根向边，那么子树里所有的边都会发生翻转。这样偶数层单子节点的根向边就和奇数层单子节点根向边颜色相同了。如下图所示。

当然，如果一棵大子树中有奇偶不同的单子点，就会导致颜色翻转时发生矛盾，这样的情况就无法用两种颜色完成染色，必须要用三种。

所以我们在实现时，先判断是否会产生矛盾，如果不会，就用两种颜色染，如果会，就用三种颜色染。

还有一些需要特判情况：

然后这道题的构造部分就做完了。下面的交互部分就会简单很多。

首先，我们记录每种颜色的边数是否为 1。我们把“是 1”记成 1，“不是 1”记成 0，然后就可以列出一个类似“真值表”的东西。

红 蓝 绿 选择
1 1 0 红
0 1 1 蓝
1 0 1 绿
1 0 0 红
0 1 0 蓝
0 0 1 绿

然后根据真值表选择颜色即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,DEP,K,rt[10001],dep[10001],col[10001];
vector<int> son[1001];
void dfs(int x,int fa){
    rt[x]=fa;//rt 记录所在大子树的根节点 
    DEP=max(DEP,dep[x]);//记录数的高度 
    for(auto y:son[x]){
        dep[y]=dep[x]+1;
        dfs(y,fa);
    }
}
bool check(){
    if(DEP==1)return 0;//只有两层for循环进不去 
    for(int i=2;i<=n;++i)
        if(son[i].size()==1){//单子节点 
            if((~col[rt[i]])&&col[rt[i]]!=(dep[i]&1))return 0;//矛盾了 
            col[rt[i]]=dep[i]&1;//根据层数奇偶性 
        }
    return 1;
}
void color_2(int x){//染两种颜色 
    if(col[x]==-1)col[x]=0;
    for(auto y:son[x]){
        if(x!=1)col[y]=col[x]^1;
        color_2(y);
    }
    if(col[x]==0)col[x]=2;
}
void color_3(int x){//染三种颜色 
    if(x!=1)col[x]=dep[x]%3;
    for(auto y:son[x])color_3(y);
}
int main(){
    cin>>n;
    for(int i=2;i<=n;++i){
        int par;
        scanf("%d",&par);
        son[par].push_back(i);
    }
    for(auto y:son[1])dep[y]=1,dfs(y,y);
    memset(col,0xff,sizeof(col));
    if(check()){
        K=2;
        cout<<"2\n";
        color_2(1);
    }
    else{
        K=min(3,DEP);//注意特判 
        cout<<K<<"\n";
        color_3(1);
    }
    for(int i=2;i<=n;++i)
        cout<<(col[i]+2)%3+1<<" ";
    cout<<endl;
    while(1){
        int sta,ec[4]={0,0,0,0}; 
        scanf("%d",&sta);
        if(sta==1||sta==-1)return 0;
        for(int i=1;i<=K;++i){
            int tmp;
            scanf("%d",&tmp);
            if(tmp==1)ec[i]=1;//标注为 1 
        }
        if(ec[1]&&!ec[3])cout<<"1";
        else if(ec[2])cout<<"2";
        else cout<<"3";
        cout<<endl;
    }
}