题目
n(n<=5e5)个点的以1为根的有根树，每条边上有一个'a'到'v'的字母(即字母种数=22)
称一条路径(u,v)是合法的，当且仅当这条路径上的字母，能经过重排形成回文串
对于每个点u，求u的子树内最长的合法路径
思路来源
https://www.luogu.com.cn/blog/Soulist/solution-cf741d
题解
考虑重排构成回文串，当且仅当其字符数量均为偶数或者恰好有一个奇数，
用01表示其奇偶性，对于22种字符，先按位状压成[0,(1<<22)-1]的一个整数
则(u,v)的路径合法，当且仅当的值是0，2的1次方，2的2次方，...，2的21次方，
由于异或性质，，则只需考察u到根1的链，v到根1的链
开一个1<<22大小的桶，用于记录当前重儿子桶里异或值为x的最大深度为now[x]，
这样对于一个u到根的异或值y，如果存在x^y==0，x^y==2的1次方，……，说明可以更新答案，
启发式合并复杂度O(nlogn)，check及更新答案23次操作，即O(23nlogn)
答案分三种，
1.两个点均来自轻儿子/重儿子子树中
2.一个点是根，一个点是儿子
3.一个点在重儿子树(及已经挂上去的轻儿子)上，另一个点为当前枚举的轻儿子
启发式合并，感觉是把答案拆成两半维护，
对于当前枚举的节点，高效地去找那另一半与其能拼凑成答案的值
代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define SZ(x) (int)(x.size())
#define sci(x) scanf("%d",&(x))
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
ll modpow(ll x,ll n,ll mod){ll res=1;for(;n;n>>=1,x=x*x%mod)if(n&1)res=res*x%mod;return res;}
const db eps=1e-8,PI=acos(-1.0);
const int N=5e5+10,M=(1<<22)+5,INF=0x3f3f3f3f,mod=1e9+7;//998244353
vector<P>E[N];
int n,f;
char s[5];
ll ans[N],dis[N],d[N],now[M];//now i:表示子树里链异或值为i的最大深度为nowi
int sz[N];
int st[N],ed[N],dfn[N],tot;
void dfs(int u,int fa){
sz[u]=1;
st[u]=++tot;
dfn[tot]=u;
for(P x:E[u]){
int v=x.fi,w=x.se;
if(v!=fa){
dis[v]=dis[u]^w;
d[v]=d[u]+1;
dfs(v,u);
sz[u]+=sz[v];
}
}
ed[u]=tot;
}
void dfs(int u,int fa,bool keep){
int mx=-1,son=-1;
for(P x:E[u]){
int v=x.fi,w=x.se;
if(v!=fa&&sz[v]>mx)
mx=sz[v],son=v;
}
for(P x:E[u]){
int v=x.fi,w=x.se;
if(v!=fa&&v!=son){
dfs(v,u,0);
ans[u]=max(ans[u],ans[v]);//1.来自轻儿子
}
}
if(son!=-1){
dfs(son,u,1);
ans[u]=max(ans[u],ans[son]);//1.来自重儿子
}
for(P x:E[u]){
int v=x.fi,w=x.se;
if(v!=fa&&v!=son){
for(int i=st[v];i<=ed[v];i++){
int x=dfn[i];
if(now[dis[x]]){
ans[u]=max(ans[u],now[dis[x]]+d[x]-2*d[u]);//2.把轻儿子往u所在重儿子子树上挂 统计异或为0的答案
}
for(int k=0;k<22;++k){
if(now[dis[x]^(1<<k)]){
ans[u]=max(ans[u],now[dis[x]^(1<<k)]+d[x]-2*d[u]);//2.把轻儿子往u所在重儿子子树上挂 统计二进制仅一位的答案
}
}
}
for(int i=st[v];i<=ed[v];i++){
int x=dfn[i];
now[dis[x]]=max(now[dis[x]],d[x]);
}
}
}
if(now[dis[u]]){//3.以根为一端的一条链 异或为0 异或二进制仅一位
ans[u]=max(ans[u],now[dis[u]]-d[u]);
}
for(int k=0;k<22;++k){
if(now[dis[u]^(1<<k)]){
ans[u]=max(ans[u],now[dis[u]^(1<<k)]-d[u]);
}
}
now[dis[u]]=max(now[dis[u]],d[u]);
if(keep==0){
for(int i=st[u];i<=ed[u];i++){
int x=dfn[i];
now[dis[x]]=0;
}
}
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;++i){
scanf("%d%s",&f,s);
int w=1<<(s[0]-'a');
E[f].pb(P(i,w));//E[i].pb(P(fa,w));
}
dfs(1,-1);
dfs(1,-1,0);
for(int i=1;i<=n;++i)
printf("%lld%c",ans[i]," \n"[i==n]);
return 0;
}
