又是玄学的dsu on tree ，这次还用到了二进制状压的思想......
用二进制压一个x表示根到节点的链上的字符信息，奇数个为1，偶数个为0。
那么如果x的二进制表示里有不多于一个1，那么重排后就能形成回文串啦。
对于两条链，如果想合并信息，异或一下就OK。
这个题很难想啊......
简单地说，就是子树里乱搞啦~哈哈哈~
然后用dsu on tree搞一下，据说用(dfs序+for循环)代替(dfs深搜子树)，能大幅优化常数。
其实思路也不是很烧脑，盯着代码想一想就差不多了吧。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define maxn 500005 5 using namespace std; 6 7 int n; 8 int hd[maxn],nx[maxn<<1],to[maxn<<1],c[maxn<<1],cnt; 9 int sz[maxn],dep[maxn],x[maxn],f[1<<23],ans[maxn]; 10 int st[maxn],ed[maxn],fnd[maxn],ord; 11 12 void edge(int af,int at,int ac) 13 { 14 to[++cnt]=at; 15 c[cnt]=ac; 16 nx[cnt]=hd[af]; 17 hd[af]=cnt; 18 } 19 20 void pre(int p,int fa,int ec) 21 { 22 st[p]=++ord; 23 fnd[ord]=p; 24 sz[p]=1; 25 dep[p]=dep[fa]+1; 26 x[p]=(x[fa]^(1<<ec)); 27 for(int i=hd[p];i;i=nx[i]) 28 { 29 if(to[i]==fa)continue; 30 pre(to[i],p,c[i]); 31 sz[p]+=sz[to[i]]; 32 } 33 ed[p]=ord; 34 } 35 36 void dfs(int p,int fa,int stay) 37 { 38 int son=0,mx=-1; 39 for(int i=hd[p];i;i=nx[i]) 40 { 41 if(to[i]==fa)continue; 42 if(sz[to[i]]>mx)mx=sz[to[i]],son=to[i]; 43 } 44 for(int i=hd[p];i;i=nx[i]) 45 { 46 if(to[i]==fa||to[i]==son)continue; 47 dfs(to[i],p,0); 48 ans[p]=max(ans[p],ans[to[i]]); 49 } 50 if(son)dfs(son,p,1),ans[p]=max(ans[p],ans[son]); 51 if(f[x[p]])ans[p]=max(ans[p],f[x[p]]-dep[p]); 52 for(int i=0;i<22;i++) 53 if(f[x[p]^(1<<i)]) 54 ans[p]=max(ans[p],f[x[p]^(1<<i)]-dep[p]); 55 f[x[p]]=max(f[x[p]],dep[p]); 56 for(int i=hd[p];i;i=nx[i]) 57 { 58 if(to[i]==fa||to[i]==son)continue; 59 for(int j=st[to[i]];j<=ed[to[i]];j++) 60 { 61 if(f[x[fnd[j]]]) 62 ans[p]=max(ans[p],f[x[fnd[j]]]+dep[fnd[j]]-2*dep[p]); 63 for(int k=0;k<22;k++) 64 { 65 if(f[x[fnd[j]]^(1<<k)]) 66 ans[p]=max(ans[p],f[x[fnd[j]]^(1<<k)]+dep[fnd[j]]-2*dep[p]); 67 } 68 } 69 for(int j=st[to[i]];j<=ed[to[i]];j++) 70 { 71 f[x[fnd[j]]]=max(f[x[fnd[j]]],dep[fnd[j]]); 72 } 73 } 74 if(!stay)for(int i=st[p];i<=ed[p];i++)f[x[fnd[i]]]=0; 75 } 76 77 int main() 78 { 79 scanf("%d",&n); 80 for(int i=2;i<=n;i++) 81 { 82 int t; 83 char s[5]; 84 scanf("%d",&t); 85 scanf("%s",s+1); 86 edge(i,t,s[1]-'a'); 87 edge(t,i,s[1]-'a'); 88 } 89 pre(1,0,0); 90 dfs(1,0,1); 91 for(int i=1;i<=n;i++)printf("%d ",ans[i]); 92 return 0; 93 }