# [树上启发式合并 &amp;&amp; 哈希] Codeforces 741D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

xiaoxiao2021-02-28  10

#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; }