You are given a tree (a connected acyclic undirected graph) of n vertices. Vertices are numbered from 1 to n and each vertex is assigned a character from a to t.
A path in the tree is said to be palindromic if at least one permutation of the labels in the path is a palindrome.
For each vertex, output the number of palindromic paths passing through it.
Note: The path from vertex u to vertex v is considered to be the same as the path from vertex v to vertex u, and this path will be counted only once for each of the vertices it passes through.
The first line contains an integer n (2 ≤ n ≤ 2·105) — the number of vertices in the tree.
The next n - 1 lines each contain two integers u and v (1 ≤ u, v ≤ n, u ≠ v) denoting an edge connecting vertex u and vertex v. It is guaranteed that the given graph is a tree.
The next line contains a string consisting of n lowercase characters from a to t where the i-th (1 ≤ i ≤ n) character is the label of vertex i in the tree.
Print n integers in a single line, the i-th of which is the number of palindromic paths passing through vertex i in the tree.
5
1 2
2 3
3 4
3 5
abcbb
1 3 4 3 3
7
6 2
4 3
3 7
5 2
7 2
1 4
afefdfs
1 4 1 1 2 4 2
In the first sample case, the following paths are palindromic:
2 - 3 - 4
2 - 3 - 5
4 - 3 - 5
Additionally, all paths containing only one vertex are palindromic. Listed below are a few paths in the first sample that are not palindromic:
1 - 2 - 3
1 - 2 - 3 - 4
1 - 2 - 3 - 5
题意：给你一颗 n 个顶点的树（连通无环图）。顶点从 1 到 n 编号，并且每个顶点对应一个在‘a’到‘t’的字母。 树上的一条路径是回文是指至少有一个对应字母的排列为回文。 对于每个顶点，输出通过它的回文路径的数量。 注意：从u到v的路径与从v到u的路径视为相同，只计数一次。
题解：
首先是一个结论
本题要求路径的某个排列为回文串，很显然，路径上最多有一个字母出现奇数次。只需要记录奇偶性显然可以用状压去解决。
根据这个结论，我们可以推出对于一个点u，他到某个点v的路径如果满足条件，显然状压的数字等于0或者1<<i(i<=19)，这个时候可以考虑搞出一个中点k，于是问题等价于dis(u,k)^dis(v,k)等于0或者1<<i(i<=19)
这显然是点分治的思路
考虑点分治中的暴力怎么写：首先对于重心进行dfs，求出所有点到重心的dis，dis表示路径上个字母的奇偶性，并且记录 dis_idisi 的数量。
接着对于每棵子树将该子树对所有dis的数量贡献全部去掉，再对该子树进行dfs，对于每个点的dis，统计与他异或等于0或者1<<i(i<=19)的数量，即为该点贡献答案，值得注意的是，经过该点的路径一定经过其父节点，因为是从另一颗子树中跑过来的，所以在dfs返回的时候应该给父节点加上子节点的贡献。接着把该子树的dis全部加回去跑下一棵子树。
因为每个点本身都是一个回文串，所以最后答案要加一。
代码如下：
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define poi void
#define int long long
using namespace std; vector<int> g[];
char c[];
int n,ans[],a[],size[],vis[],f[],tmp[(<<)|]; poi get_size(int now,int fa)
{
size[now]=;
f[now]=fa;
for(int i=;i<g[now].size();i++)
{
if(vis[g[now][i]]||g[now][i]==fa) continue;
get_size(g[now][i],now);
size[now]+=size[g[now][i]];
}
} int get_zx(int now,int fa)
{
if(size[now]==) return now;
int son,maxson=-;
for(int i=;i<g[now].size();i++)
{
if(vis[g[now][i]]||g[now][i]==fa) continue;
if(maxson<size[g[now][i]])
{
maxson=size[g[now][i]];
son=g[now][i];
}
}
int zx=get_zx(son,now);
while(size[zx]<*(size[now]-size[zx])) zx=f[zx];
return zx;
} poi get(int now,int fa,int sta,int kd)
{
sta^=(<<a[now]);
tmp[sta]+=kd;
for(int i=;i<g[now].size();i++)
{
if(vis[g[now][i]]||g[now][i]==fa) continue;
get(g[now][i],now,sta,kd);
}
} int calc(int now,int fa,int sta)
{
sta^=(<<a[now]);
int num=tmp[sta];
for(int i=;i<=;i++)
{
num+=tmp[sta^(<<i)];
}
for(int i=;i<g[now].size();i++)
{
if(vis[g[now][i]]||g[now][i]==fa) continue;
num+=calc(g[now][i],now,sta);
}
ans[now]+=num;
return num;
} poi solve(int now)
{
vis[now]=;
get(now,,,);
long long num=tmp[];
for(int i=;i<=;i++)
{
num+=tmp[<<i];
}
for(int i=;i<g[now].size();i++)
{
if(vis[g[now][i]]) continue;
get(g[now][i],,<<a[now],-);
num+=calc(g[now][i],,);
get(g[now][i],,<<a[now],);
}
ans[now]+=num/;
get(now,,,-);
for(int i=;i<g[now].size();i++)
{
if(vis[g[now][i]]) continue;
get_size(g[now][i],);
int zx=get_zx(g[now][i],);
solve(zx);
}
} signed main()
{
scanf("%lld",&n);
for(int i=;i<n;i++)
{
int from,to;
scanf("%lld%lld",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
scanf("%s",c+);
for(int i=;i<=n;i++)
{
a[i]=c[i]-'a';
}
solve();
for(int i=;i<=n;i++)
{
printf("%lld ",ans[i]+);
}
}