一棵根为1 的树，每条边上有一个字符（a-v共22种）。 一条简单路径被称为Dokhtar-kosh当且仅当路径上的字符经过重新排序后可以变成一个回文串。 求每个子树中最长的Dokhtar-kosh路径的长度。
如果重排后能构成回文串，那么出现奇数次的字符最多一个。用一个22位二进制数表示每一个字母出现的次数的奇偶，把一个点到根节点的路径的异或值记为$s[u]$，那么就是在子树里找到两个点使其$s$值异或之后1的个数不超过1个，那么用dsu on tree就可以了
记得最后别忘了用儿子的答案更新自己的
//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf -0x3f3f3f3f
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}
int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
inline char getch(){
char ch;while((ch=getc())>'z'||ch<'a');return ch;
}
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
void print(int x){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]=' ';
}
const int N=5e5+;
int head[N],Next[N<<],ver[N<<],tot;
inline void add(int u,int v){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
}
int sz[N],d[N],son[N],s[N],ans[N],f[N*],a[N];char c[N];
int mx,n,bin[];
void dfs1(int u,int fa){
sz[u]=,d[u]=d[fa]+,s[u]=s[fa]^bin[a[u]];
for(int i=head[u];i;i=Next[i]){
int v=ver[i];dfs1(v,u);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u]=v;
}
}
void calc(int rt,int u){
int now=s[u];cmax(mx,f[now]+d[u]-*d[rt]);
if((s[u]^s[rt])==) cmax(mx,d[u]-d[rt]);
for(int i=;i<;++i){
now=bin[i]^s[u];
cmax(mx,f[now]+d[u]-*d[rt]);
if((s[u]^s[rt])==bin[i]) cmax(mx,d[u]-d[rt]);
}
for(int i=head[u];i;i=Next[i]) calc(rt,ver[i]);
}
void update(int u,int k){
k?cmax(f[s[u]],d[u]):f[s[u]]=inf;
for(int i=head[u];i;i=Next[i]) update(ver[i],k);
}
void dfs2(int u,int k){
for(int i=head[u];i;i=Next[i])
if(ver[i]!=son[u]) dfs2(ver[i],);
if(son[u]) dfs2(son[u],);
mx=;int now=s[u];
cmax(mx,f[now]-d[u]);
for(int i=;i<;++i)
now=bin[i]^s[u],cmax(mx,f[now]-d[u]);
for(int i=head[u];i;i=Next[i])
if(ver[i]!=son[u]) calc(u,ver[i]),update(ver[i],);
ans[u]=mx;
if(!k){
for(int i=head[u];i;i=Next[i]) update(ver[i],);
f[s[u]]=inf;
}else cmax(f[s[u]],d[u]);
}
void spread(int u){
for(int i=head[u];i;i=Next[i]){
int v=ver[i];spread(v);
cmax(ans[u],ans[v]);
}
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();
bin[]=;for(int i=;i<=;++i) bin[i]=bin[i-]<<;
for(int i=;i<=n;++i){
int u=read();c[i]=getch();
add(u,i),a[i]=c[i]-'a';
}
dfs1(,);
memset(f,0xef,sizeof(f));
dfs2(,);spread();
for(int i=;i<=n;++i) print(ans[i]);
return Ot(),;
}