vp 时候想到大致思路了，但是死活调不对，赛后套取 cf 的数据调了好久才过/ll
首先直觉告诉我们答案不会太大。稍微猜一猜可以猜出除了四个点的菊花之外答案都是 \(n\bmod 2\)，下面我们来通过构造证明这件事情。
首先，链的情况是 trivial 的，直接根据奇偶性间隔染色即可。如果不是链，那么必然存在一个三度点 \(R\)，不妨以 \(R\) 为根。对于一种染色方案记 \(dif_x\) 表示 \(x\) 子树内与 \(x\) 颜色相同的点的颜色个数 \(-\) 与 \(x\) 不相同的点的颜色个数，那么我们考虑先对除根节点之外的其他节点染色，使得对于任意 \(x\ne R\) 都有 \(-1\le dif_x\le 2\)，并且任意非叶节点都存在一个儿子颜色与其不同。具体方案是，DFS 到一个节点 \(x\) 时，递归染其子树，然后先令 \(x\) 所有儿子颜色都相同（不妨设为白色），而 \(x\) 自己染成黑色，此时显然 \(dif_x=1-\sum\limits_{y\in son_x}dif_y\)，不难发现如果 \(x\) 的儿子个数 \(\le 1\) 此时已经满足条件了，否则由于一个点最多两个儿子，必然有 \(-3\le dif_x\le 3\)。如果 \(dif_x\le -2\)，必然存在一个儿子 \(dif_y=2\)，全局翻转这个子树，同理如果 \(dif_x=3\) 说明两个儿子 \(dif\) 都是 \(-1\)，全局翻转任意一个即可。由于这两种情况我们翻转的都不是叶节点（叶节点的 \(dif\) 值为 \(1\)），因此翻转完之后必然合法。具体实现见下面代码里的 dfs2 和 dfs3。
接下来考虑加入根节点进行调整。首先先将根节点三个儿子都染成白色，根节点自己染成黑色，不妨设其三个儿子为 \(a,b,c\)，那么此时不平衡度为 \(|dif_a+dif_b+dif_c-1|\)，记 \(S=dif_a+dif_b+dif_c-1\)，那么我们希望将 \(S\) 调整成 \(-1\le S\le 1\) 的状态。如果此时已经满足就好办了，否则根据 \(-1\le dif_a,dif_b,dif_c\le 2\) 可知此时 \(-4\le S\le 5\)，但是稍微分析下就知道如果 \(S\le -3\) 必然存在某个儿子 \(dif=-1\)，我们就不断对 \(dif=-1\) 的儿子进行子树全局翻转直到满足 \(-1\le S\le 1\) 即可。同理如果 \(S\ge 3\) 必然存在某个儿子 \(dif=2\)，也不断翻转即可。比较麻烦的是 \(S=-2\)，因为可能出现某个儿子 \(dif=1\)，此时它有可能是叶子节点，直接翻转会导致这个点没有相邻的异色节点。因此分情况讨论：
- 如果三个儿子的 \(dif\) 都是 \(1\)，由于特判掉了四个点的菊花，所以必然存在一个儿子 \(siz\ge 3\)，全局翻转这个即可。
- 如果三个儿子的 \(dif\) 分别是 \(0,1,2\)，那么如果这个 \(1\) 对应的 \(siz\ge 3\)，全局翻转这个儿子，否则这个 \(1\) 是孤立点。那么考虑这个 \(dif=2\) 的儿子，不妨设为 \(a\)，如果 \(a\) 和 \(R\) 颜色相同就先翻转 \(R\) 和 \(R\) 的孤立点儿子，接着考虑 \(a\)，如果 \(a\) 不存在任何一个儿子为孤立点，那么直接翻转 \(a\) 即可。否则考虑 \(a\) 的非叶子儿子 \(a'\)，根据 \(dif_{a'}=dif_a=2\) 可知 \(a\) 颜色与 \(a'\) 相同，因此我们先翻转 \(a\) 和 \(a\) 的叶子儿子，然后递归考虑 \(a'\) 直到不存在非叶子儿子即可。具体实现见代码里的
FLIP函数。
时间复杂度线性。
const int MAXN=2e5;
int n,fa[MAXN+5],deg[MAXN+5];vector<int>g[MAXN+5];
int dep[MAXN+5],res[MAXN+5];bool in[MAXN+5];
void dfs1(int x,int f){for(int y:g[x])if(y!=f)dep[y]=dep[x]+1,dfs1(y,x);}
int tag[MAXN+5],siz[MAXN+5],dif[MAXN+5];
void dfs2(int x,int f){
siz[x]=1;dif[x]=1;
for(int y:g[x])if(y!=f){dfs2(y,x);siz[x]+=siz[y];tag[y]=1;dif[x]-=dif[y];}
if(dif[x]==3){for(int y:g[x])if(y!=f&&dif[y]==-1){tag[y]=0;dif[x]+=2*dif[y];break;}}
else if(dif[x]<=-2){for(int y:g[x])if(y!=f&&dif[y]==2){tag[y]=0;dif[x]+=2*dif[y];break;}}
}
void dfs3(int x,int f){for(int y:g[x])if(y!=f)res[y]=res[x]^tag[y],dfs3(y,x);}
void dfs4(int x,int f){res[x]^=1;for(int y:g[x])if(y!=f)dfs4(y,x);}
void FLIP(int x,int f){
int sum=0,A=0;
for(int y:g[x])if(y!=f&&siz[y]==1)sum++,A=y;
if(!sum)res[x]^=1;
else{
for(int y:g[x])if(y!=f){
if(siz[y]!=1&&dif[y]==2){
if(res[x]!=res[y]){res[x]^=1;res[A]^=1;}
FLIP(y,x);
}
}
}
}
void solve(){
scanf("%d",&n);
for(int i=2;i<=n;i++)scanf("%d",&fa[i]);
for(int i=1;i<=n;i++)g[i].clear(),deg[i]=res[i]=tag[i]=0;
for(int i=2;i<=n;i++){
deg[i]++;deg[fa[i]]++;
if(i==4){
bool flg=0;
for(int j=1;j<=i;j++)flg|=(deg[j]==3);
if(flg)puts("2");
else puts("0");
}else printf("%d\n",i%2);
}
for(int i=2;i<=n;i++)g[i].pb(fa[i]),g[fa[i]].pb(i);
int rt=0;for(int i=1;i<=n;i++)if(deg[i]==3)rt=i;
if(!rt){
dfs1(1,0);
for(int i=1;i<=n;i++)res[i]=(dep[i]&1);
}else{
int sum=-1;res[rt]=1;
for(int y:g[rt])dfs2(y,rt),sum+=dif[y],dfs3(y,rt);
if(n==4)goto print;
if(sum<=-2){
for(int y:g[rt])if(dif[y]==-1&&sum<=-2){sum-=2*dif[y];dfs4(y,rt);}
}else if(sum>=3){
for(int y:g[rt])if(dif[y]==2){sum-=2*dif[y];dfs4(y,rt);break;}
}else if(sum==2){
bool flg=0;
for(int y:g[rt])if(siz[y]>1&&siz[y]%2){dfs4(y,rt);flg=1;break;}
if(!flg)FLIP(rt,0);
}
}
print:
for(int i=1;i<=n;i++)putchar(res[i]?'w':'b');
putchar('\n');
}
int main(){int qu;scanf("%d",&qu);while(qu--)solve();return 0;}