CF914E Palindromes in a Tree

做这题时智商下线，掰着手指数’a’到’t’有多少个字母都数错了。真是狗屎。

顺便重学了点分治？

传送门

首先虽然这个题说的很不清楚，但它的回文串和我们一般说的回文串是不一样的，在这个题里，一个串是回文的当且仅当其中至多一个字母出现次数为奇数。同时，如果你不像我一样傻叉的话，你会发现’a’到’t’一共有19个字母。

那么我们可以状压存一个串每个字母的奇偶性，然后上点分治。

点分治的具体实现方法就是先把一个分治中心子树中所有串状压开个桶存下来，然后枚举每个子树，把其中的串在桶中删去。dfs这个子树计算贡献，由于问的是在回文串上点的个数，所以每次统计一个点要加上这次统计中这个点儿子的答案。这样分治中心会被$u->v$的路径和$v->u$的路径算两次，所以分治中心统计的时候除个2。以及单个字符也是个回文串，所以每个点的答案再加一。

关于具体计数的实现见代码。

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
struct node{
    int next,to;
}w[400001];
int size[200001],head[200001],vis[200001];
int maxn[200001],all,rt,a[200001],n,cnt;
ll o[1<<20],ans[200001];
char ch[200001];
inline void add(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; head[x]=cnt;
}
void get_rt(int x,int fa){
    size[x]=1; maxn[x]=0;
    for (int i=head[x]; i; i=w[i].next){
        if (w[i].to!=fa&&!vis[w[i].to]){
            get_rt(w[i].to,x);
            size[x]+=size[w[i].to];
            maxn[x]=max(maxn[x],size[w[i].to]);
        }
    }
    maxn[x]=max(maxn[x],all-size[x]);
    if (maxn[x]<maxn[rt]) rt=x;
}
void dfs(int x,int fa,int y,int dis){
    dis^=(1<<a[x]); o[dis]+=y;
    for (int i=head[x]; i; i=w[i].next)
        if (w[i].to!=fa&&!vis[w[i].to])
            dfs(w[i].to,x,y,dis);
}
ll get_dis(int x,int fa,int l){
    l^=(1<<a[x]); ll num=o[l];
    for (int i=0; i<=19; i++) num+=o[l^(1<<i)];
    for (int i=head[x]; i; i=w[i].next){
        if (w[i].to!=fa&&!vis[w[i].to]){
            num+=get_dis(w[i].to,x,l);
        }
    }
    ans[x]+=num;
    return num;
}
void calc(int x){
    vis[x]=1;
    dfs(x,0,1,0);
    // for (int i=head[x]; i; i=w[i].next){
    // 	if (vis[w[i].to]) continue;
    // 	dfs(w[i].to,x,1,1<<a[w[i].to]);
    // }
    ll num=o[0];
    for (int i=0; i<=19; i++) num+=o[1<<i];
    for (int i=head[x]; i; i=w[i].next){
        if (vis[w[i].to]) continue;
        dfs(w[i].to,x,-1,1<<a[x]);
        num+=get_dis(w[i].to,x,0);
        dfs(w[i].to,x,1,1<<a[x]);
    }
    dfs(x,0,-1,0); ans[x]+=num/2;
}
void solve(int x){
    calc(x);
    for (int i=head[x]; i; i=w[i].next){
        if (vis[w[i].to]) continue;
        rt=0; all=size[w[i].to];
        get_rt(w[i].to,0); solve(rt);
    }
}
int main(){
    int x,y;
    scanf("%d",&n);
    for (int i=1; i<n; i++){
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    scanf("%s",ch+1);
    for (int i=1; i<=n; i++) a[i]=ch[i]-'a';
    maxn[0]=1e9; all=n; get_rt(1,0);
    solve(rt);
    for (int i=1; i<=n; i++) printf("%I64d ",ans[i]+1);
    return 0;
}