【题意】给定一棵树，每个点都有一个a~t的字符，一条路径回文定义为路径上的字符存在一个排列构成回文串，求经过每个点的回文路径数。n<=2*10^5。
【算法】点分治
【题解】状压20位的二进制表示一条路径的字符状态，点分治过程中维护扫描过的路径只须维护状态桶数组，t[i]表示前面状态为i的路径条数。
合并：考虑当前状态为j，要使合并的状态满足条件即i^j=1<<k（0<=k<20）或i^j=0，移项得i=j^(1<<k)或i=j，所以路径数是Σ t [ j^(1<<k) ]+t[j]。
统计每个点：对于当前要处理的重心x，先遍历所有子树得到整个t[]数组，然后对每个子树先删除其在桶里的状态，然后扫一遍贡献子树中每个点，最后将子树的状态加回桶中。
这样可以做到每条路径都贡献到每个点，要特殊处理重心的贡献。
复杂度O(n log n)。
#include<cstdio>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=,maxN=;
int tot,first[maxn],sz[maxn],vis[maxn],sum,root,a[maxn],u,v,n;
ll ans[maxn],t[maxN];
struct edge{int v,from;}e[maxn*]; void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
void getroot(int x,int fa){
sz[x]=;
bool ok=;
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa&&!vis[e[i].v]){
getroot(e[i].v,x);
sz[x]+=sz[e[i].v];
if(sz[e[i].v]>sum/)ok=;
}
if(ok&&sz[x]>=sum/)root=x;
}
void dfs(int x,int fa,int p,int s){
t[s^=(<<a[x])]+=p;
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa&&!vis[e[i].v])dfs(e[i].v,x,p,s);
}
ll calc(int x,int fa,int s){
s^=(<<a[x]);ll num=t[s];
for(int i=;i<;i++)num+=t[s^(<<i)];
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa&&!vis[e[i].v])num+=calc(e[i].v,x,s);
ans[x]+=num;
return num;
}
void solve(int x,int s){
vis[x]=;
dfs(x,,,);
ll num=t[];
for(int i=;i<;i++)num+=t[<<i];
for(int i=first[x];i;i=e[i].from)if(!vis[e[i].v]){
dfs(e[i].v,x,-,<<a[x]);
num+=calc(e[i].v,x,);
dfs(e[i].v,x,,<<a[x]);
}
ans[x]+=num/;
dfs(x,,-,);
for(int i=first[x];i;i=e[i].from)if(!vis[e[i].v]){
if(sz[e[i].v]>sz[x])sum=s-sz[x];else sum=sz[e[i].v];
getroot(e[i].v,x);
solve(root,sum);
}
}
char s[maxn];
int main(){
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
insert(u,v);insert(v,u);
}
scanf("%s",s+);
for(int i=;i<=n;i++)a[i]=s[i]-'a';
sum=n;
getroot(,);
solve(root,sum);
for(int i=;i<=n;i++)printf("%lld ",ans[i]+);
return ;
}