AGRA TASK WITH HASH_TABLE

// God & me
// "Someone like you" ? Unbelievable ...
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 17, z = 26, inf = 1e9;
vector<int> adj[maxn], near_mask[maxn];
int n, big[maxn], a[maxn], sz[maxn], cur, ans[maxn], h[maxn], bag[maxn], tmp[maxn];
int st[maxn], ft[maxn], ver[maxn], dfs_time;
char s[maxn];
void pre_dfs(int v = 0){
    st[v] = dfs_time++;
    ver[ st[v] ] = v;
    sz[v] = 1, big[v] = -1;
    for(auto u : adj[v]){
	a[u] = (1 << s[u] - 'a') ^ a[v];
	h[u] = h[v] + 1;
	pre_dfs(u);
	sz[v] += sz[u];
	if(big[v] == -1 || sz[u] > sz[ big[v] ])
	    big[v] = u;
    }
    ft[v] = dfs_time;
}
void dfs(int v = 0, bool cl = 0){
    for(auto u : adj[v])
	if(u != big[v])
	    dfs(u, 1), ans[v] = max(ans[v], ans[u]);
    if(big[v] != -1)
	dfs(big[v], 0), ans[v] = max(ans[v], ans[ big[v] ]);
    for(auto u : adj[v])
	if(u != big[v]){
	    for(int p = st[u]; p < ft[u]; p++){
		int x = ver[p];
		for(auto mask : near_mask[ a[x] ])
		    cur = max(cur, h[x] + bag[mask] - 2 * h[v]);
	    }
	    for(int p = st[u]; p < ft[u]; p++)
		bag[ a[ ver[p] ] ] = max(bag[ a[ ver[p] ] ], h[ ver[p] ]);
	}
    for(auto mask : near_mask[ a[v] ])
	cur = max(cur, bag[mask] - h[v]);
    bag[ a[v] ] = max(bag[ a[v] ], h[v]);
    ans[v] = max(ans[v], cur);
    if(cl){
	for(int p = st[v]; p < ft[v]; p++)
	    bag[ a[ ver[p] ] ] = -inf;
	cur = 0;
    }
}
const int V=2000003;
bitset<1 << 26> has;
int sta[V],ky[V];
struct Hash_table{  // adapted from TooDifficult code
    int fst[V], nxt[V];
    int T,p;
    void init() {
	T=1; p=0;
    }
    void insert(int s) {
	if(has[s])  return ;
	int S=s%V;
	nxt[T]=fst[S],fst[S]=T,sta[T]=s,ky[T++]=p++;
    }
    int query(int s) {
	for (int j=fst[s%V];j;j=nxt[j]) if (sta[j]==s) return ky[j];
    }
}Hash;
void init(){
    copy(a, a + n, tmp);
    sort(tmp, tmp + n);
    int sz = unique(tmp, tmp + n) - tmp;
    Hash.init();
    for(int i = 0; i < sz; i++)
	Hash.insert(tmp[i]), has.set(tmp[i]);
    for(int i = 0; i < sz; i++){
	near_mask[i].push_back(i);
	for(int b = 0; b < z; b++)
	    if(has.test(tmp[i] ^ (1 << b)))
		near_mask[i].push_back(Hash.query(tmp[i] ^ (1 << b)));
    }
    for(int i = 0; i < n; i++)
	a[i] = Hash.query(a[i]);
}
int main(){
    scanf("%d", &n);
    for(int i = 1, p; i < n; i++){
	scanf("%d %c", &p, &s[i]), p--;
	adj[p].push_back(i);
    }
    fill(begin(bag), end(bag), -inf);
    pre_dfs();
    init();
    dfs();
    for(int i = 0; i < n; i++)  printf("%d ", ans[i]);
    return 0;
}