题意:一棵以$1$为根的树上,每条边都有一个$a$到$v$之间的字母
一条路径被称为“好路径”当且仅当其上字母可以经过重新排序后成为一个回文串。
对于每个子树,求出其中最长的“好路径”的长度。
------------
把字母转化为边权$dis=2^{ch-'a'}$
一条路径称为“好路径”的条件就是:这条路径的边权异或和在二进制下最多有一个$1$
对于每个子树都要计算答案,$dp$和数据结构好像都难以完成
好像还有一个奇妙的东西?树上$dsu$!
类似淀粉质,开一个桶,$f[i]$表示从根开始异或和为$i$的最大深度
预处理出每个子树的$dfs$序
先递归处理轻儿子,删除轻儿子的贡献,递归处理重儿子,把轻儿子再算一遍
```
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=5e5+5;
struct node
{
int to,nxt,dis;
}edge[N<<1];
int n,num,head[N],dep[N],dis[N],tot[N],idx[N],a[N];
int tim,L[N],R[N],son[N],ans[N],f[1<<22];
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline void add_edge(int from,int to,int dis)
{
edge[++num]=(node){to,head[from],dis};
head[from]=num;
}
void dfs(int k,int fa)
{
a[idx[k]=L[k]=++tim]=k; tot[k]=1; dep[k]=dep[fa]+1;
for (reg int i=head[k],bigson=0;i;i=edge[i].nxt)
{
int v=edge[i].to,d=edge[i].dis;
dis[v]=dis[k]^d; dfs(v,k); tot[k]+=tot[v];
if (bigson<tot[v]) bigson=tot[v],son[k]=v;
}
R[k]=tim;
}
void DFS(int k,bool flag)
{
for (reg int i=head[k];i;i=edge[i].nxt)
{
int v=edge[i].to;
if (v!=son[k]) DFS(v,0),ans[k]=max(ans[k],ans[v]);
}
if (son[k]) DFS(son[k],1),ans[k]=max(ans[k],ans[son[k]]);
if (f[dis[k]]) ans[k]=max(ans[k],f[dis[k]]-dep[k]);
for (reg int i=0;i<22;i++)
if (f[dis[k]^(1<<i)]) ans[k]=max(ans[k],f[dis[k]^(1<<i)]-dep[k]);
f[dis[k]]=max(f[dis[k]],dep[k]);
for (reg int i=head[k];i;i=edge[i].nxt)
{
int v=edge[i].to;
if (v==son[k]) continue;
for (reg int j=L[v];j<=R[v];j++)
{
if (f[dis[a[j]]]) ans[k]=max(ans[k],f[dis[a[j]]]+dep[a[j]]-(dep[k]<<1));
for (reg int c=0;c<22;c++)
if (f[dis[a[j]]^(1<<c)]) ans[k]=max(ans[k],f[dis[a[j]]^(1<<c)]+dep[a[j]]-(dep[k]<<1));
}
for (reg int j=L[v];j<=R[v];j++) f[dis[a[j]]]=max(f[dis[a[j]]],dep[a[j]]);
}
if (!flag) for (reg int i=L[k];i<=R[k];i++) f[dis[a[i]]]=0;
}
int main()
{
n=read();
for (reg int i=2;i<=n;i++)
{
int x=read();
char c=getchar();
while (c<'a'||c>'v') c=getchar();
add_edge(x,i,(1<<(c-'a')));
}
dfs(1,0); DFS(1,0);
for (reg int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
```