日常VP翻车
学一发树上启发式合并，%%%gjghfd 树上启发式合并可以截这里
每次递归做轻儿子，做完后清空轻儿子信息（注意是做完一个轻儿子后发现清空这个），然后做重儿子，再dfs所有轻儿子并跟新当前点的答案，然后把轻儿子信息加进去……
说起来很绕，其实挺好理解的… 每个节点的哈希值就是它到根路径哪些字符出现奇数次，记录就是记录每个哈希值的深度的最大值，然后类似求路径长度搞一搞就好了
#include <cstdio> #include <iostream> #include <algorithm> #include <tr1/unordered_map> #include <vector> #define fi first #define se second using namespace std; using namespace tr1; typedef pair<int,int> ii; const int N=500010; int n,ans[N],a[N],hs[N],dpt[N],son[N],sz[N],f[1<<23]; vector<ii> s[N]; inline void fix(int &x,int y){ if(x<y) x=y; } void dfs(int x){ sz[x]=1; for(ii i : s[x]){ hs[i.fi]=hs[x]^(1<<i.se); dpt[i.fi]=dpt[x]+1; dfs(i.fi); sz[x]+=sz[i.fi]; if(sz[i.fi]>sz[son[x]]) son[x]=i.fi; } } void del(int x){ f[hs[x]]=0; for(ii i : s[x]) del(i.fi); } void add(int x){ for(ii i : s[x]) add(i.fi); fix(f[hs[x]],dpt[x]); } void check(int x,int u){ if(f[hs[x]]) fix(ans[u],dpt[x]+f[hs[x]]-2*dpt[u]); for(int i=0;i<22;i++) if(f[hs[x]^(1<<i)]) fix(ans[u],dpt[x]+f[hs[x]^(1<<i)]-2*dpt[u]); for(ii i : s[x]) check(i.fi,u); } void solve(int x){ for(ii i : s[x]){ int u=i.fi; if(u!=son[x]) solve(u),del(u); } if(son[x]) solve(son[x]); for(ii i : s[x]){ int u=i.fi; fix(ans[x],ans[u]); if(u!=son[x]) check(u,x),add(u); } fix(ans[x],f[hs[x]]-dpt[x]); for(int j=0;j<22;j++) fix(ans[x],f[hs[x]^(1<<j)]-dpt[x]); fix(f[hs[x]],dpt[x]); } int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); scanf("%d",&n); for(int i=2;i<=n;i++){ int p; char c; scanf("%d %c",&p,&c); s[p].push_back(ii(i,c-'a')); } dfs(1); solve(1); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }