// https://codeforces.com/contest/741/problem/D

//? 與下題類似

// https://ac.nowcoder.com/acm/contest/4853/E??旗鼓相當(dāng)?shù)膶?duì)手

#include "stdafx.h"

//#include <bits/stdc++.h>

#include<cstdio>

#include<cstring>

#include<iostream>

#include <algorithm>?

#include <vector>?

using namespace std;

typedef long long ll;

const int N = 5e5+4;

?

int n,cur;

vector<pair<int,int>> adj[N];

int son[N];

int L[N],R[N],V[N],sz[N],h[N],dis[N];

int d[1<<22],ans[N];

void dfs1(int u){?

sz[u] = 1;// 子樹大小

V[L[u] = cur++] = u;

for (auto i : adj[u]){

h[i.first] = h[u] + 1;// 頂點(diǎn)深度, 根的深度為0

dis[i.first] = dis[u]^(1<<i.second);// 路徑上的字母統(tǒng)計(jì)(只保留2的余數(shù))

dfs1(i.first);?

sz[u] += sz[i.first];

if(sz[i.first] > sz[son[u]]) son[u]=i.first;

}

R[u] = cur;//? 子樹dfs編號(hào)結(jié)束位置

cout<<dis[u]<<", u="<<u<<endl;

}

void path(int v,int u){?

cout<<dis[u]<<", u="<<u<<", h[v]="<<h[v]<<",h[u]="<<h[u]<<endl;

//? 假設(shè)另外一個(gè)頂點(diǎn)x， dis[x]^dis[v]? 必須是0 或者 1<<i(字母相同， 或者相差一個(gè)字母),

//? 則x與v的路徑上字母可以組成回文。

//? 頂點(diǎn)x的深度是d[dis[v]]或者d[dis[v]^(1<<i)]， 所以x與v的路徑長度(x與v在u的不同分支)：

//? d[dis[v]] + h[v] - 2*h[u] 或者 d[dis[v]^(1<<i)] + h[v] - 2*h[u]

//? 如果u是1的話，h[u]=0， x與v的路徑長度即為兩者深度之和

if(d[dis[v]])ans[u] = max(ans[u], d[dis[v]] + h[v] - 2*h[u]);

cout<<ans[u]<<", d[dis[v]]="<<d[dis[v]]<<",v="<<v<<endl;

for (int i=0; i<22; i++)

{

if(d[dis[v]^(1<<i)])ans[u] = max(ans[u], d[dis[v]^(1<<i)] + h[v] - 2*h[u]);

//if(u==1 && v==5)cout<<ans[u]<<", [dis[v]]="<<(dis[v]^(1<<i))<<endl;

}

cout<<"ans[u]="<<ans[u]<<", d[dis[v]]="<<d[dis[v]]<<endl;

}

void dfs2(int u,bool f){

ans[u] = 0;?

for (auto i : adj[u])?

if (i.first != son[u]){

dfs2(i.first, 0); ans[u] = max(ans[u], ans[i.first]);

}

if (son[u]){

dfs2(son[u], 1);?

ans[u] = max(ans[u], ans[son[u]]);

path(u, u);

}

d[dis[u]] = max(d[dis[u]], h[u]);// 字母集合達(dá)到的最大深度

cout<<"深度：u="<<u<<", dis[u]="<<dis[u]<<", d[dis[u]]="<<d[dis[u]]<<endl;

for (auto i: adj[u])?

if (i.first != son[u]){

for (int k=L[i.first]; k<R[i.first]; k++) path(V[k], u);

for (int k=L[i.first]; k<R[i.first]; k++)

d[dis[V[k]]] = max(d[dis[V[k]]], h[V[k]]);// 字母集合達(dá)到的最大深度

}

if (!f)

for (int i=L[u]; i<R[u]; i++) d[dis[V[i]]] = 0;

}

int main(){

//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

n=6;

//cin >> n;

int ar[8][2]={

1, 'c',

2, 'b',

1, 'c',

4, 'b',

1,'a'

};

for (int i=2,a; i<=n; i++){?

char c;?

//cin >> a >> c;

a=ar[i-2][0];

c=ar[i-2][1];

adj[a].push_back(make_pair(i, c-'a'));

}

//h[1]=1;

dfs1(1);

dfs2(1, 1);

for (int i=1; i<=n; i++) cout << ans[i] << " "; cout << "\n";

return 0;

}

? ? ? ? ? ? ? ? ? ?