题目链接：Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
第一次写\(dsu\ on\ tree\)，来记录一下
\(dsu\ on\ tree\)主要维护子树信息，往往可以省掉一个数据结构的启发式合并。大体思路如下：
轻重链路径剖分之后，对每个点先递归处理他的所有轻儿子，每次处理完轻儿子之后把这棵子树的信息清空。最后再来处理重孩子，重儿子的信息就可以不用清空了。由于我们是用一个全局数组来记录信息的，重儿子子树的信息就仍然保留在全局数组中。接着我们另外写一个函数\(dfs\)所有的轻儿子子树，并统计答案。每统计完一棵子树的答案就可以把这棵子树的信息计入全局数组中，用于下一次更新。由于每个点到根的轻边条数是\(\log n\)级别的，所以每个点最多被扫\(\log n\)遍。
回到这道题上来。由于要求路径上的所有字符重新排列之后可以形成一个回文串，也就是说出现次数为奇数的字符不会超过\(1\)个。那么我们就可以给每个字符一个\(2^x\)形式的权值，这样的话合法路径的异或和要么为\(0\)，要么为\(2^x\)的形式。
设点\(x\)到根的异或和为\(D_x\)，由于这道题是边权，\(x\)和\(y\)路径上的异或和就可以用\(D_x\ xor\ D_y\)来表示。这样的话就可以用一个数组\(c\)来统计答案，其中\(c_i\)表示满足\(D_x=i\)的\(x\)的最大深度。剩下的就是套\(dsu\ on\ tree\)的板子了。
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 500010
#define INF (1<<30) using namespace std;
typedef long long llg; int n,ci[1<<22],son[maxn],siz[maxn],dep[maxn];
int hd[maxn],nt[maxn],D[maxn],ans[maxn]; int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=1;
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
} void dfs(int u){
siz[u]=1;
for(int i=hd[u];i;i=nt[i]){
D[i]^=D[u]; dep[i]=dep[u]+1;
dfs(i); siz[u]+=siz[i];
if(siz[i]>siz[son[u]]) son[u]=i;
}
} void undo(int u){
ci[D[u]]=-INF;
for(int i=hd[u];i;i=nt[i]) undo(i);
} int o;
void up(int &x,int y){if(y>x) x=y;}
void up(int u){
up(ans[o],dep[u]+ci[D[u]]);
for(int i=0;i<=21;i++) up(ans[o],dep[u]+ci[1<<i^D[u]]);
for(int i=hd[u];i;i=nt[i]) up(i);
} void ins(int u){
up(ci[D[u]],dep[u]);
for(int i=hd[u];i;i=nt[i]) ins(i);
} void work(int u){
for(int i=hd[u];i;i=nt[i])
if(i!=son[u]) work(i),undo(i);
if(son[u]) work(son[u]); o=u;
for(int i=hd[u];i;i=nt[i])
if(i!=son[u]) up(i),ins(i);
up(ci[D[u]],dep[u]);
up(ans[u],dep[u]+ci[D[u]]);
for(int i=0;i<=21;i++) up(ans[u],dep[u]+ci[1<<i^D[u]]);
ans[u]-=dep[u]<<1;
for(int i=hd[u];i;i=nt[i]) up(ans[u],ans[i]);
} int main(){
File("a");
n=getint();
for(int i=0;i<(1<<22);i++) ci[i]=-INF;
for(int i=2,x;i<=n;i++){
x=getint();
nt[i]=hd[x];hd[x]=i;
char c=getchar();
while(c>'v' || c<'a') c=getchar();
D[i]=1<<(c-'a');
}
dfs(1); work(1);
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}