- Note
- 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[200010];
- char c[200010];
- int n,ans[200010],a[200010],size[200010],vis[200010],f[200010],tmp[(1<<20)|10];
- poi get_size(int now,int fa)
- {
- size[now]=1;
- f[now]=fa;
- for(int i=0;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]==1) return now;
- int son,maxson=-1;
- for(int i=0;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]<2*(size[now]-size[zx])) zx=f[zx];
- return zx;
- }
- poi get(int now,int fa,int sta,int kd)
- {
- sta^=(1<<a[now]);
- tmp[sta]+=kd;
- for(int i=0;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^=(1<<a[now]);
- int num=tmp[sta];
- for(int i=0;i<=19;i++)
- {
- num+=tmp[sta^(1<<i)];
- }
- for(int i=0;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]=1;
- get(now,0,0,1);
- long long num=tmp[0];
- for(int i=0;i<=19;i++)
- {
- num+=tmp[1<<i];
- }
- for(int i=0;i<g[now].size();i++)
- {
- if(vis[g[now][i]]) continue;
- get(g[now][i],0,1<<a[now],-1);
- num+=calc(g[now][i],0,0);
- get(g[now][i],0,1<<a[now],1);
- }
- ans[now]+=num/2;
- get(now,0,0,-1);
- for(int i=0;i<g[now].size();i++)
- {
- if(vis[g[now][i]]) continue;
- get_size(g[now][i],0);
- int zx=get_zx(g[now][i],0);
- solve(zx);
- }
- }
- signed main()
- {
- scanf("%lld",&n);
- for(int i=1;i<n;i++)
- {
- int from,to;
- scanf("%lld%lld",&from,&to);
- g[from].push_back(to);
- g[to].push_back(from);
- }
- scanf("%s",c+1);
- for(int i=1;i<=n;i++)
- {
- a[i]=c[i]-'a';
- }
- solve(1);
- for(int i=1;i<=n;i++)
- {
- printf("%lld",ans[i]+1);
- }
- }
来源: http://www.bubuko.com/infodetail-2717801.html