[CF1879E] Interactive Game with Coloring 题解

· · 题解

很诡谲的一道题。

首先特判菊花，答案为 1。

不难发现题目要求每次行动都往父亲走，这显然表明父亲边的颜色必须与这个点连的其他边不同，这个条件是必要的。

根据这个条件可以发现，如果树上没有链，即每个点要么是叶子要么有两个儿子，那么可以令 \text{col}_i=\text{dep}_i\bmod 2+1，这样一定能赢。

如果有链，则可能出现多个点连边颜色可重集为 \{1,2\}，同时这些点中有一些父亲边是 1，有一些是 2，这时无法判断怎么往父亲走。于是 k=2 不一定正确。调整发现 k=3 一定正确，令 \text{col}_i=\text{dep}_i\bmod 3+1，则一个链上的点的颜色集合，与父亲边在哪一个颜色，是一一对应的。

现在问题在于如何判断能否 k=2，不难发现 1 的所有子树相互独立，于是对每个子树分别判断。对于链上且不是端点的点，其颜色集合一定为 \{1,2\}，不妨强制令其往颜色 1 走（注意这个强制是同时应用于整棵树的），这样链上的边颜色就有了明确的限制。然后枚举子树顶端向根 1 的连边涂 1 还是 2，这样直接确定了一整颗子树的颜色，直接判能不能使得链上非端点的点满足上文的限制即可。

视实现，复杂度在 \mathcal{O}(n)\sim\mathcal{O}(n^2) 左右，不过这个东西并不重要。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
const ll maxn=107,p=1e9+7,ee=1e18;
ll n,k,k1,k2,c[maxn],dep[maxn],buc[maxn],fs[maxn];
ll siz[maxn],dfn[maxn],L,R,dnt;
vector<ll> edge[maxn];
void dfs1(ll u){
    siz[u]=1,dfn[u]=++dnt;
    for(auto v:edge[u]) dep[v]=dep[u]+1,dfs1(v),siz[u]+=siz[v];
}
bool check(ll x){
    L=dfn[x],R=dfn[x]+siz[x]-1;
    for(ll i=1;i<=n;i++)if(L<=dfn[i]&&dfn[i]<=R) c[i]=(dep[i]&1)+1;
    ll flg=1;
    for(ll i=1;i<=n;i++)if(L<=dfn[i]&&dfn[i]<=R&&edge[i].size()==1&&c[i]!=1){flg=0; break;}
    if(flg) return 1;
    for(ll i=1;i<=n;i++)if(L<=dfn[i]&&dfn[i]<=R) c[i]=((dep[i]+1)&1)+1;
    flg=1;
    for(ll i=1;i<=n;i++)if(L<=dfn[i]&&dfn[i]<=R&&edge[i].size()==1&&c[i]!=1){flg=0; break;}
    return flg;
}
bool check2(void){
    for(auto x:edge[1])if(!check(x)) return 0;
    return 1;
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(ll i=2,u;i<=n;i++) cin>>u,fs[i]=u,edge[u].pb(i);
    dfs1(1);
    if(*max_element(fs+2,fs+1+n)==1){
        k=1;
        for(ll i=2;i<=n;i++) c[i]=1;
    }else{
        if(!check2()){
            k=3;
            for(ll i=1;i<=n;i++) c[i]=dep[i]%3+1;
        }else k=2;
    }
    cout<<k<<endl;
    for(ll i=2;i<=n;i++) cout<<c[i]<<" "; cout<<endl;
    for(ll st;;){
        cin>>st;
        if(st!=0) exit(0);
        for(ll i=1;i<=k;i++) cin>>buc[i];
        if(k==1) cout<<1<<endl;
        else if(k==2){
            if(!buc[1]) cout<<2<<endl;
            else if(!buc[2]) cout<<1<<endl;
            else if(buc[1]==1) cout<<1<<endl;
            else cout<<2<<endl;
        }else if(k==3){
            if(buc[1]&&buc[2]) cout<<1<<endl;
            else if(buc[1]&&buc[3]) cout<<3<<endl;
            else if(buc[2]&&buc[3]) cout<<2<<endl;
            else for(ll i=1;i<=k;i++)if(buc[i]==1){
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;
}

::::