设标'a'的点为红色点，标'b'的点为蓝色点。

设$d$为所有点中到点$1$的距离种类数，则答案只可能是$d$或者$d+1$。

如果答案为$d$等价于可以使得同深度的点颜色相同，可以用随机化解决。

具体来说：维护一个集合，如果集合中所有数的和小于$x$就随机加入一个数，否则随机删除一个数。

这么随机一次找到答案的概率为$\frac{1}{n}$，随机$100n$次就可以过了。

答案为$d+1$即：存在一组方案使得最多有一种深度存在两种不同的颜色，且有儿子的节点全部是同一种颜色。

因为如果颜色不同就会导致两个儿子对应的字符串不同。

这种情况一定有解，下面用构造法证明：

假设深度为$i$的点一共有$num_{i,0}$个有儿子的，$num_{i,1}$个没有儿子的，深度大于等于$i$的节点共$sum_i$个。

则明显$sum_{i+1} \geq num_{i,1}$，因为每一个有儿子的点对应至少一个深度更大的点。

假设用第$i+1$层到第$d$层的点可以构造出有$x \in [0,sum_{i+1}]$个红色点的答案，然后需要用第$i$层到第$d$层的点中构造有$y$个红色点的答案。

如果$y \leq sum_{i+1}$直接沿用之前的方案，如果$y \geq sum_i-sum_{i+1}$就把$i$层点选上，然后套用之前的方案。

如果$sum_{i+1} \leq y \leq sum_i-sum_{i+1}$，则有$num_{i,1} \leq y \leq num_{i,0}+num{i,1}$，直接选$y$个第$i$层的点即可。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#include<vector>
int n,d,n0,n1,t,cnt=-1;
int fir[100000],to[200000],nxt[200000];
int dep[100000],f[2][100000],num[2][100001];
int sum[100000]; bool son[100000];
vector<int> nd[2][100000];
char ans[100000];
void add(int a,int b)
{
    to[++cnt]=b;
    nxt[cnt]=fir[a];
    fir[a]=cnt;
    return;
}
void dfs(int i)
{
    for(int j=fir[i];j!=-1;j=nxt[j]){
        dep[to[j]]=dep[i]+1;
        dfs(to[j]);
    }
    return;
}

#include<cstdlib>
#include<ctime>
struct A{
    int val,id;
}a[100000];
bool solve1(int m)
{
    for(int i=0;i<d;i++){
        a[i].id=i;
        a[i].val=num[0][i]+num[1][i];
    }
    srand(time(NULL));
    int pos=0,S=0,lim=100*n;
    while(lim--){
        if(S==m) break;
        if(S<m){
            int t=rand()%(d-pos)+pos;
            S+=a[t].val;
            swap(a[pos],a[t]); pos++;
        }
        else{
            int t=rand()%pos;
            S-=a[t].val;
            pos--; swap(a[pos],a[t]);
        }
    }
    if(S==m){
        for(int i=0;i<d;i++)
            f[0][i]=f[1][i]=0;
        for(int i=0;i<d;i++)
            if(i<pos) f[0][a[i].id]=a[i].val;
            else f[1][a[i].id]=a[i].val;
        return 1;
    }
    return 0;
}

void init(void)
{
    scanf("%d%d",&n,&n0);
    n1=n-n0;
    for(int i=0;i<n;i++)
        fir[i]=-1;
    for(int i=1;i<n;i++){
        scanf("%d",&t);
        add(t-1,i); son[t-1]=1;
    }
    dep[0]=0; dfs(0);
    for(int i=0;i<n;i++)
        if(son[i]){
            f[1][dep[i]]++; num[1][dep[i]]++;
            nd[1][dep[i]].push_back(i);
        }
        else{
            f[0][dep[i]]++; num[0][dep[i]]++;
            nd[0][dep[i]].push_back(i);
        }
    for(d=0;num[0][d]+num[1][d]>0;d++);
    sum[d-1]=num[0][d-1]+num[1][d-1];
    for(int i=d-2;i>=0;i--)
        sum[i]=sum[i+1]+num[0][i]+num[1][i];
    return;
}

void solve2(int dep,int tar,char c0,char c1)
{
    int num2=num[0][dep]+num[1][dep];
    if(dep==d-1){
        f[c0-'a'][dep]=tar;
        f[c1-'a'][dep]=num2-tar;
        return;
    }
    if(0<=tar&&tar<=sum[dep+1]){
        solve2(dep+1,tar,c0,c1);
        f[c0-'a'][dep]=0; f[c1-'a'][dep]=num2;
    }
    else if(num[1][dep]<=tar&&tar<=num2){
        solve2(dep+1,0,c0,c1);
        f[c0-'a'][dep]=tar; f[c1-'a'][dep]=num2-tar;
    }
    else{
        solve2(dep+1,sum[dep]-tar,c1,c0);
        f[c0-'a'][dep]=num2; f[c1-'a'][dep]=0;
    }
    return;
}

int main(void)
{
    init();
    if(!solve1(n0)){
        solve2(0,n0,'a','b');
        printf("%d\n",d+1);
    }
    else printf("%d\n",d);
    for(int i=0;i<d;i++)
        if(f[0][i]>=num[1][i]){
            for(int j=0;j<nd[1][i].size();j++)
                ans[nd[1][i][j]]='a';
            for(int j=0;j<nd[0][i].size();j++)
                if(num[1][i]+j>=f[0][i])
                    ans[nd[0][i][j]]='b';
                else ans[nd[0][i][j]]='a';
        }
        else{
            for(int j=0;j<nd[1][i].size();j++)
                ans[nd[1][i][j]]='b';
            for(int j=0;j<nd[0][i].size();j++)
                if(num[1][i]+j>=f[1][i])
                    ans[nd[0][i][j]]='a';
                else ans[nd[0][i][j]]='b';
        }
    for(int i=0;i<n;i++)
        putchar(ans[i]);
    putchar('\n');
    return 0;
}

View Code