TLE#12，救救孩子

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+10;

struct node
{
	int to,nxt;
	char c;
}ed[N];
int head[N],tot,ans[N]; 
int n;
int anss;
map<int,int> mp;
int cnt[N],dep[N],sz[N],son[N],p[N],p1;

void add(int u,int v,char c)
{
	ed[++tot].nxt=head[u];
	ed[tot].to=v;
	ed[tot].c=c;
	head[u]=tot;
}

void dfss(int x,int fa)
{
	sz[x]=1;
	for(int i=head[x];i;i=ed[i].nxt)
	{
		int y=ed[i].to;
		if(y==fa)continue;
		dep[y]=dep[x]+1;
		int now=ed[i].c-'a';
		cnt[y]=cnt[x]^(1<<(now));
		dfss(y,x);
		sz[x]+=sz[y];
		if(sz[son[x]]<sz[y])son[x]=y;
	} 
}

void update(int x,int fa,int rt)
{
	for(int i=0;i<22;i++)
	{
		int s=cnt[x]^(1<<i);
		if(mp.count(s)!=0)anss=max(anss,mp[s]+dep[x]-2*dep[rt]);
	}
	int s=cnt[x];
	if(mp.count(s)!=0)anss=max(anss,mp[s]+dep[x]-2*dep[rt]);
	p[++p1]=x;
	for(int i=head[x];i;i=ed[i].nxt)
	{
		int y=ed[i].to;
		if(y==fa)continue;
		update(y,x,rt);
	}
}

void addd(int x)
{
	if(mp.count(cnt[x])==0||mp[cnt[x]]<dep[x])mp[cnt[x]]=dep[x];
}

void dfs(int x,int fa,int op)
{
	for(int i=head[x];i;i=ed[i].nxt)
	{
		int y=ed[i].to;
		if(y==fa||y==son[x])continue;
		dfs(y,x,0);
		ans[x]=max(ans[x],ans[y]);
	}
	if(son[x])dfs(son[x],x,1),ans[x]=max(ans[x],ans[son[x]]);
	for(int i=head[x];i;i=ed[i].nxt)
	{
		int y=ed[i].to;
		if(y==fa||y==son[x])continue;
		update(y,x,x);
		while(p1)addd(p[p1--]);
	}
	for(int i=0;i<22;i++)
	{
		int s=cnt[x]^(1<<i);
		if(mp.count(s)!=0)anss=max(anss,mp[s]-dep[x]);
	}
	int s=cnt[x];
	anss=max(anss,mp[s]-dep[x]);
	ans[x]=max(anss,ans[x]);
	//printf("ans:%d\n",anss);
	if(!op)mp.clear(),anss=0;
	else addd(x);
}

int main()
{
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		int fa;
		char c;
		scanf("%d",&fa);
		cin>>c;
		add(fa,i,c);
	}
	dep[1]=1;
	dfss(1,0); 
	dfs(1,0,1);
	for(int i=1;i<=n;i++)
	{
		printf("%d ",ans[i]);
	}
	return 0;
}