这题精妙的一点就是将通过把性质（最多一位是奇数）转化成前缀和异或和，之后任意两点之间的数量就是异或值。
这样我们把每条边的权值都当成1<<i即可。因为我们要对每个点计算答案，所以需要用树上启发式合并，也就是保留重儿子，遍历所有其他节点。
对于一个点的答案，他有三个来源，1是直接子树中的答案，2是以u为根的答案，3是穿过u的两条路径异或和。
对于第二种，其实就是因为我们直接保留的重儿子要计算，其他的都可以直接归到第三种上去
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; int h[N],ne[N],e[N],w[N],idx; int pre[N],ed[N],times,id[N]; int ans[N]; int sz[N],son[N]; int st[N]; int flag; int dis[N],f[N*10]; int depth[N]; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void dfs1(int u,int fa){ sz[u]=1; int i; depth[u]=depth[fa]+1; pre[u]=++times; id[times]=u; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; dis[j]=dis[u]^w[i]; dfs1(j,u); sz[u]+=sz[j]; if(sz[j]>sz[son[u]]){ son[u]=j; } } ed[u]=times; } void cal(int u){ if(f[dis[u]]) ans[u]=max(ans[u],f[dis[u]]-depth[u]); int i; for(i=0;i<=21;i++){ if(f[dis[u]^(1<<i)]) ans[u]=max(ans[u],f[dis[u]^(1<<i)]-depth[u]); } f[dis[u]]=max(f[dis[u]],depth[u]); for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==flag) continue; int x; for(x=pre[j];x<=ed[j];x++){ int num=id[x]; if(f[dis[num]]){ ans[u]=max(ans[u],f[dis[num]]+depth[num]-2*depth[u]); } for(int v=0;v<=21;v++){ if(f[dis[num]^(1<<v)]){ ans[u]=max(ans[u],f[dis[num]^(1<<v)]+depth[num]-2*depth[u]); } } } for(x=pre[j];x<=ed[j];x++){ f[dis[id[x]]]=max(f[dis[id[x]]],depth[id[x]]); } } } void dfs(int u,int keep){ int i; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==son[u]) continue; dfs(j,0); ans[u]=max(ans[u],ans[j]); } if(son[u]){ dfs(son[u],1); flag=son[u]; ans[u]=max(ans[u],ans[son[u]]); } cal(u); flag=0; if(!keep){ for(i=pre[u];i<=ed[u];i++){ f[dis[id[i]]]=0; } } } int main(){ ios::sync_with_stdio(false); memset(h,-1,sizeof h); int n; cin>>n; int i; for(i=2;i<=n;i++){ int x; cin>>x; char c; cin>>c; add(x,i,1<<(c-'a')); } dfs1(1,0); dfs(1,1); for(int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl; return 0; }