题意: 给定一个以 11 为根的 n 个节点的树, 每个点上有一个字母 (a~z), 每个点的深度定义为该节点到 11 号节点路径上的点数. 每次询问 a,ba,b 查询以 aa 为根的子树内深度为 bb 的节点上的字母重新排列之后是否能构成回文串.
分析: 很明显是个树上启发式合并. 显然, 只要深度为 bb 结点的所有颜色中, 至多有一种的数量为奇数就可以构成回文串了.
- #include<bits/stdc++.h>
- using namespace std;
- #define pb push_back
- typedef long long ll;
- const int M=5e5+5;
- int sz[M],son[M],deep[M],w[M],countt[M][30],ans[M],vis[M];
- char s[M];
- vector<int>g[M];
- vector<pair<int,int>>Q[M];
- void dfs1(int u,int fa){
- sz[u]=1;
- deep[u]=deep[fa]+1;
- for(int i=0;i<g[u].size();i++){
- int v=g[u][i];
- dfs1(v,u);
- sz[u]+=sz[v];
- if(sz[v]>sz[son[u]])
- son[u]=v;
- }
- }
- void update(int u,int k){
- countt[deep[u]][w[u]]+=k;
- for(int i=0;i<g[u].size();i++){
- int v=g[u][i];
- if(!vis[v])
- update(v,k);
- }
- }
- void dfs2(int u,int sign){
- for(int i=0;i<g[u].size();i++){
- int v=g[u][i];
- if(v!=son[u])
- dfs2(v,0);
- }
- if(son[u])
- dfs2(son[u],1),vis[son[u]]=1;
- update(u,1);
- for(int i=0;i<Q[u].size();i++){
- int num=0;
- int id=Q[u][i].first;
- int d=Q[u][i].second;
- for(int j=0;j<26;j++){
- if(countt[d][j]&1)
- num++;
- }
- if(num>1)
- ans[id]=0;
- else
- ans[id]=1;
- }
- vis[son[u]]=0;
- if(!sign)
- update(u,-1);
- }
- int main(){
- int n,m;
- scanf("%d%d",&n,&m);
- for(int u,i=2;i<=n;i++){
- scanf("%d",&u);
- g[u].pb(i);
- }
- scanf("%s",s);
- for(int i=0;i<n;i++)
- w[i+1]=s[i]-'a';
- for(int u,v,i=1;i<=m;i++){
- scanf("%d%d",&u,&v);
- Q[u].pb(make_pair(i,v));
- }
- dfs1(1,0);
- dfs2(1,0);
- for(int i=1;i<=m;i++)
- if(ans[i])
- printf("Yes\n");
- else
- printf("No\n");
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3394802.html