这是我最难导出来的一次，昨天一整天从早导到晚，实在导不出来了，有没有大佬帮我导一下

感激不尽，给关注QWQ.

mp就是当"map"用的，但是那样会超时，所以写了数组形式。

#include<bits/stdc++.h>
#define ll long long
#define MAXN 500005
#define INF LONG_LONG_MAX
using namespace std;
ll head[MAXN],egt,mp[40000005];
struct Edge{
	ll v,nxt;
	char w;
}eg[MAXN];
inline void add(ll u,ll v,char w){
	eg[++egt]={v,head[u],w};
	head[u]=egt;
}
inline ll change(char k){
	return (ll)(k-'a');
}
inline bool find_1(ll k){
	ll res=0;
	while(k){
		if(k&1)res++;
		k>>=1;
		if(res>1)return false;
	}
	return true;
}
ll siz[MAXN],son[MAXN],dep[MAXN],dis[MAXN],fas[MAXN];
inline void dfs1(ll p){
	dep[p]=dep[fas[p]]+1;
	siz[p]=1;
	mp[dis[p]]=-INF;
	for(ll d=head[p];d;d=eg[d].nxt){
		ll v=eg[d].v;
		char w=eg[d].w;
		dis[v]=dis[p]^(1<<change(w));
		dfs1(v);
		siz[p]+=siz[v];
		if(siz[v]>siz[son[p]])son[p]=v;
	}
}
ll n,ans[MAXN],now;
inline void get(ll p){
	if(mp[dis[p]]!=-INF)
		ans[now]=max(ans[now],dep[p]+mp[dis[p]]-dep[now]-dep[now]);
	for(ll i=0;i<=21;i++){
		ll asd=dis[p]^(1<<i);
		if(mp[asd]!=-INF)
			ans[now]=max(ans[now],dep[p]+mp[asd]-dep[now]-dep[now]);
	}
	for(ll i=head[p];i;i=eg[i].nxt){
		ll v=eg[i].v;
		get(v);
	}
}
inline void add(ll p){
	mp[dis[p]]=max(mp[dis[p]],dep[p]);
	for(ll i=head[p];i;i=eg[i].nxt){
		ll v=eg[i].v;
		add(v);
	}
}
inline void del(ll p){
	mp[dis[p]]=-INF;
	for(ll i=head[p];i;i=eg[i].nxt){
		ll v=eg[i].v;
		del(v);
	}
}
inline void dfs2(ll p,ll opt){
//	cout<<"p = "<<p<<endl;
	for(ll i=head[p];i;i=eg[i].nxt){
		ll v=eg[i].v;
		if(v==son[p])continue;
		dfs2(v,0);
	}
	if(son[p])dfs2(son[p],1);
	now=p;
	if(son[p])mp[dis[son[p]]]=max(mp[dis[son[p]]],dep[son[p]]);
	for(ll i=head[p];i;i=eg[i].nxt){
		ll v=eg[i].v;
		ans[p]=max(ans[p],ans[v]);
		if(v==son[p])continue;
		get(v);
		add(v);
	}
	if(son[p]){
//		cout<<"p = "<<p<<endl;
		ll asd=dis[p];
		if(mp[asd]!=-INF){
//			cout<<"asd = "<<asd<<endl;
			ans[p]=max(ans[p],mp[asd]-dep[p]);
		}
		for(ll i=0;i<=21;i++){
			ll qwe=asd^(1<<i);
//			cout<<"qwe = "<<qwe<<endl;
			if(mp[qwe]!=-INF) 
			ans[p]=max(ans[p],mp[qwe]-dep[p]);
		}
	}
	if(!opt)del(p);	
}
char adw;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(ll i=2;i<=n;i++){
		cin>>fas[i]>>adw;
		add(fas[i],i,adw);
	}
	dfs1(1);
	for(ll i=1;i<=n;i++){
		cout<<"i = "<<i<<"   son = "<<son[i]<<"   dis = "<<dis[i]<<endl;
	} 
	dfs2(1,1);
	for(ll i=1;i<=n;i++)cout<<ans[i]<<" ";
	return 0;
}