题目
题目链接：https://codeforces.com/problemset/problem/914/E
题意 给你一颗 \(n\) 个顶点的树（连通无环图）。顶点从 \(1\) 到 \(n\) 编号，并且每个顶点对应一个在 ‘\(a\)’ 到 ‘\(t\)’ 的字母。树上的一条路径是回文是指至少有一个对应字母的排列为回文。对于每个顶点，输出通过它的回文路径的数量。注意：从 \(u\) 到 \(v\) 的路径与从 \(v\) 到\(u\) 的路径视为相同，只计数一次。
思路
树上的数数题，无脑上点分治。
一些字符可以组成回文串的前提是最多有一个字符出现次数是奇数。而且发现只有 20 个字母，所以考虑状压，二进制下第 \(i\) 位为 1 表示第 \(i\) 个字母有奇数个。
当分治到 \(x\) 为根的时候，我们遍历 \(x\) 所有的子树，求出 \(state[S]\) 表示 \(x\) 到其子树的所有路径中，状态为 \(S\) 的路径条数。
接下来枚举每一个子节点 \(y\)。将 \(y\) 子树内的路径计数从 \(state\) 中删去，然后再次遍历。假设遍历到 \(z\in \operatorname{sub}(y)\) 时的状态为 \(s\)，那么能与 \(x\to z\) 的路径产生贡献的路径数量就有 \(\sum^{19}_{i=0}state[s \operatorname{xor } 2^i]+state[s]\) 条。
那么访问到每一个 \(y\) 后代时就求有多少条 \(x\) 其他子树的路径能与这条路径产生贡献并记录在这个节点中。容易发现这是差分后的答案。那么从下往上求和即可。
注意经过 \(x\) 的任意路径 \(y\to z\) 和 \(z\to y\) 会计算两遍。所以根节点要除以 2。但是 \(x\to y\) 只会计算一遍，直接除以二就错了。所以我们把所有 \(x\to y\) 的路径先加上。手动让他计算两遍。这样除以二就只剩一遍了。
注意要开 long long。因为没开 long long 调了一个多小时。
时间复杂度 \(O(n\log n)\)。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=200010,M=(1<<20),Inf=1e9;
int n,tot,sum,rt,head[N],state[M],a[N],size[N],maxp[N];
ll ans[N];
bool vis[N];
char ch;
struct edge
{
int next,to;
}e[N*2];
void add(int from,int to)
{
e[++tot].to=to;
e[tot].next=head[from];
head[from]=tot;
}
void findrt(int x,int fa)
{
size[x]=1; maxp[x]=0;
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (!vis[v] && v!=fa)
{
findrt(v,x);
size[x]+=size[v];
maxp[x]=max(maxp[x],size[v]);
}
}
maxp[x]=max(maxp[x],sum-size[x]);
if (maxp[x]<maxp[rt]) rt=x;
}
void dfs1(int x,int fa,int S,int val)
{
state[S]+=val;
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (!vis[v] && v!=fa) dfs1(v,x,S^a[v],val);
}
}
ll dfs2(int x,int fa,int S)
{
size[x]=1;
ll cnt=state[S];
for (int i=0;i<20;i++)
cnt+=state[S^(1<<i)];
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (!vis[v] && v!=fa)
{
cnt+=dfs2(v,x,S^a[v]);
size[x]+=size[v];
}
}
ans[x]+=cnt;
return cnt;
}
void calc(int x)
{
dfs1(x,0,a[x],1);
ll cnt=state[0]+1;
for (int i=0;i<20;i++)
cnt+=state[1<<i];
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (!vis[v])
{
dfs1(v,x,a[v]^a[x],-1);
cnt+=dfs2(v,x,a[v]);
dfs1(v,x,a[v]^a[x],1);
}
}
dfs1(x,0,a[x],-1);
ans[x]+=cnt/2;
}
void solve(int x)
{
calc(x); vis[x]=1;
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (!vis[v])
{
sum=size[v];
rt=0; maxp[0]=Inf;
findrt(v,x);
solve(rt);
}
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d",&n);
for (int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
for (int i=1;i<=n;i++)
{
while (ch=getchar()) if (ch>='a' && ch<='z') break;
a[i]=(1<<ch-'a');
}
rt=0; maxp[0]=Inf; sum=n;
findrt(1,0);
solve(rt);
for (int i=1;i<=n;i++)
printf("%I64d ",ans[i]);
return 0;
}