CF1879E Interactive Game with Coloring

· · 题解

被坑惨了。珍爱生命，远离构造。

Description

这是一道交互题。

你在和交互库玩这样一个游戏。给你一棵 n 个点，以 1 为根的树，其中树上每条边都被染了某种颜色。交互库把一棵棋子放在了树上除根节点外的某个位置，并告诉你与这个点相连的所有边中每种颜色出现的次数。然后你要选择一种颜色的边，令交互库沿该颜色的方向移动棋子。若有多条边均是该颜色，则由交互库来选择一条。

设起点到根节点的距离为 x，若你用 x 步把棋子移动到了根节点，则获胜。

现请你在保证能够获胜的前提下，用 最小的颜色数 对边染色，并给出方案。随后交互库与你进行上述游戏，你要对每一步给出应该选择的边直至获胜。

交互库自适应，n\le 100。

Solution

发现题意本质是构造方案，使在任意位置给出每种颜色的边数，都能唯一确定通向根的那条边。

因为如果选择某种颜色的边，且这样的边不止一条，会由交互库来选择，所以通向根的边不能与其他边颜色相同。而连向儿子的边不属于同一棵子树，它们之间选什么颜色都互不影响。为了方便地判断根所在的边，我们希望连向儿子的颜色都相同。

那么设 son_u 表示 u 的儿子数，则对于 son_u>1 的点判断是容易的：出现次数为 1 的颜色只有一个，它就是通往父亲的边。也就是说，我们只需要考虑染色方案能否使 son_u=1 的点判断出答案。令这类点叫作特殊点。

先不考虑该问题，我们只需要两种颜色，dep_u\bmod 2=1 的点到父亲的边染颜色 1，其余染颜色 2。这里发现，若特殊点的深度奇偶性均相同，则会出现，对于所有特殊点，它们连向父亲的边都是同一个颜色，我们记录这个颜色是什么即可。

考虑奇偶性不同的情况，发现此时它们连向父亲的边不是同一个颜色，无法区分。这里考虑引入第三种颜色。从根节点向下依次染色，对于非特殊点，只需保证父亲的边和儿子的边不同色即可；对于特殊点，我们钦定：若连向父亲的边颜色为 x，连向儿子的边颜色就赋成 x\bmod 3+1。即，1\to 2,2\to 3,3\to 1。那么我们根据边的种类，即可判断它们的方向关系。

看起来很对？Wrong answer on test 4.

点 1 不需要保证儿子都同色。所以如果奇偶性不同的两个特殊点不在一棵子树，可以把其中某棵子树的染色状态取反（\text{swap}(1,2)），而无需添加一种颜色。

完全没想到这点，鉴定为菜。

const int N=105;
int n,fa[N];
vector<int> e[N];
int son[N],dep[N],mx;
void dfs(int u)
{
    dep[u]=dep[fa[u]]+1; mx=max(mx,dep[u]);
    for(auto v:e[u]) dfs(v);
}
int flag[2],col[N];
namespace sub3
{
    int x[N];
    void dfs(int u)
    {
        for(auto v:e[u])
        {
            if(son[u]==1) col[v]=((col[u]+1)>3)?1:col[u]+1;
            else {for(int j=1;j<=3;j++) if(j!=col[u]) {col[v]=j;break;}}
            dfs(v);
        }
    }
    void solve()
    {
        for(auto v:e[1]) col[v]=1;
        for(auto v:e[1]) dfs(v);
        cout<<3<<endl;for(int i=2;i<=n;i++) cout<<col[i]<<" ";cout<<endl;
        // assert(false);
        while("qwq")
        {
            int op=read();
            if(op==1) return;
            assert(op!=-1);
            static int cnt[5]; int sum=0;
            for(int i=1;i<=3;i++) cnt[i]=read(),sum+=cnt[i];
            if(sum==2)
            {
                if(cnt[1]&&cnt[3]) cout<<3<<endl;
                else if(cnt[1]) cout<<1<<endl;
                else cout<<2<<endl;
            }
            else for(int i=1;i<=3;i++) if(cnt[i]==1) {cout<<i<<endl;break;}
        }
    }
}
namespace sub2
{
    int x[N],ff;
    void dfs(int u)
    {
        for(auto v:e[u])
        {
            for(int j=1;j<=2;j++) if(j!=col[u]) {col[v]=j;break;}
            if(son[u]==1&&u!=1) ff=col[u];
            dfs(v);
        }
    }
    void solve()
    {
        for(auto v:e[1]) dfs(v);
        cout<<2<<endl;for(int i=2;i<=n;i++) cout<<col[i]<<" ";cout<<endl;
        while("qwq")
        {
            int op=read();
            if(op==1) return;
            assert(op!=-1);
            static int cnt[5]; int sum=0;
            for(int i=1;i<=2;i++) cnt[i]=read(),sum+=cnt[i];
            if(sum==2) cout<<ff<<endl;
            else for(int i=1;i<=2;i++) if(cnt[i]==1) {cout<<i<<endl;break;}
        }
    }
}
void check(int u)
{
    if(son[u]==1) flag[dep[u]%2]=1;
    for(auto v:e[u]) check(v);
}
int main()
{
    n=read();
    for(int i=2;i<=n;i++) fa[i]=read(),e[fa[i]].push_back(i),son[fa[i]]++;
    dfs(1);
    if(mx==2)
    {
        cout<<1<<endl;
        for(int i=2;i<=n;i++) cout<<1<<" ";
        cout<<endl;
        int op=read(); for(int i=1;i<=1;i++) int x=read();
        cout<<1<<endl,op=read(); return 0;
    }
    int qwq=0;
    for(auto v:e[1])
    {
        flag[0]=flag[1]=0;
        check(v);
        if(flag[0]&&flag[1]) {sub3::solve();return 0;}
        col[v]=flag[1]?2:1;
    }
    sub2::solve();
    return 0;
}