【题意】给定n个点的树，每条边有一个小写字母a~v，求每棵子树内的最长回文路径，回文路径定义为路径上所有字母存在一种排列为回文串。n<=5*10^5。

【算法】dsu on tree

【题解】这题经典套路就是按照22个字母个数的奇偶性压位，然后两段路径异或起来是0或1<<j就是合法路径。

dsu的时候每个点统计其子树内经过这个点的路径，注意包括从子树到该点终止的和该点自身也要算。

那么类似点分治的方式，算完重儿子后处理一下根，然后就一棵一棵轻儿子子树和之前的子树状态桶数组统计然后加入。

传递上去的时候需要特别注意，dsu是无法支持数组的整体位移的，解决方法一般是把统计从x到子树改为从根到子树，这样所有点都是一样的，不需要位移。

当然这就需要满足信息的可减性，而深度deep和异或xor都是满足的。（xor和deep的两点间路径转两点到根路径非常经典了）

复杂度O(n log n)。

#include
      
       #include
       
        #include
        
         bool isdigit(char c){
    return c>='0'&&c<='9';}int read(){    int s=0,t=1;char c;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}using namespace std;const int maxn=500010,inf=0x3f3f3f3f;int n,sz[maxn],first[maxn],a[maxn],b[30],c[5000010],ans[maxn],w[maxn],fa[maxn],tot,deep[maxn];struct edge{
    int v,from;}e[maxn*2];void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}void p(int &x,int y){
    if(x
         
          sz[w[x]])w[x]=e[i].v;    }}void calc(int x,int tp){    for(int j=0;j<=22;j++)p(ans[tp],deep[x]+c[a[x]^b[j]]);    for(int i=first[x];i;i=e[i].from)calc(e[i].v,tp);}void add(int x,int k){    if(k)p(c[a[x]],deep[x]);    else c[a[x]]=-inf;    for(int i=first[x];i;i=e[i].from)add(e[i].v,k);}    void dfs(int x){    for(int i=first[x];i;i=e[i].from)if(e[i].v!=w[x])dfs(e[i].v);    if(w[x])dfs(w[x]);//    p(c[a[x]],deep[x]);for(int j=0;j<=22;j++)p(ans[x],deep[x]+c[a[x]^b[j]]);    for(int i=first[x];i;i=e[i].from)if(e[i].v!=w[x])calc(e[i].v,x),add(e[i].v,1);    if(x!=w[fa[x]])add(x,0);}char s[10];int main(){    n=read();    for(int i=2;i<=n;i++){        fa[i]=read();if(fa[i])insert(fa[i],i);        scanf("%s",s);a[i]=1<<(s[0]-'a');    }    b[22]=0;for(int j=0;j<=21;j++)b[j]=1<
          
           =1;i--)p(ans[fa[i]],ans[i]);    for(int i=1;i<=n;i++)printf("%d ",ans[i]);    return 0;}
          
         
        
       
      

 

即使信息满足可减性，dsu on tree也不能像点分治一样删除某棵子树信息，进去统计后再加回来。因为dsu on tree必须满足【不能遍历重儿子】，否则复杂度就会爆炸。

不过如果题目要求的是除了某棵子树外的信息，就可以做，先统计所有轻儿子做除了重儿子的，然后进重儿子后统计所有轻儿子，一个一个删除来做除了某个轻儿子的。