树上的回文 51Nod - 1513

本文主要是介绍树上的回文 51Nod - 1513，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1513

对每层的点分别按dfs序中的位置排序 然后对每个字母搞一个前缀和 对每个查询 找出该点在dfs序上对应区间的左右端点 在给定层上二分一下即可

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn=5e5+10;struct node1
{int v,next;
};struct node2
{bool gou[26];
};vector <int> pre[maxn];
vector <node2> sum[maxn];
node1 edge[maxn];
int first[maxn],val[maxn],deep[maxn],mp1[maxn],mp2[maxn];
int n,q,num;
char ch[maxn];template <class T>
inline void _cin(T &ret)
{char c;ret = 0;while((c = getchar()) < '0' || c > '9');while(c >= '0' && c <= '9'){ret = ret * 10 + (c - '0');c = getchar();}
}bool cmp(int u,int v)
{return mp1[u]<mp1[v];
}void addedge(int u,int v)
{edge[num].v=v;edge[num].next=first[u];first[u]=num++;
}void dfs(int cur)
{int i,v;pre[deep[cur]].pb(cur);mp1[cur]=++num;for(i=first[cur];i!=-1;i=edge[i].next){v=edge[i].v;deep[v]=deep[cur]+1;dfs(v);}mp2[cur]=num;
}void init()
{node2 tmp;int i,j,k;for(i=0;i<26;i++) tmp.gou[i]=0;for(i=1;i<=n;i++) sort(pre[i].begin(),pre[i].end(),cmp);for(i=1;i<=n;i++){for(j=0;j<pre[i].size();j++) sum[i].pb(tmp);for(j=0;j<pre[i].size();j++){if(j>0){for(k=0;k<26;k++) sum[i][j].gou[k]=sum[i][j-1].gou[k];}sum[i][j].gou[val[pre[i][j]]]^=1;}}
}int main()
{int i,p,h,l,r,m,pl,pr,cnt;///freopen("in.txt","r",stdin);///freopen("out.txt","w",stdout);_cin(n),_cin(q);///scanf("%d%d",&n,&q);memset(first,-1,sizeof(first));for(i=2;i<=n;i++){_cin(p);///scanf("%d",&p);addedge(p,i);}scanf("%s",ch);for(i=0;i<n;i++) val[i+1]=ch[i]-'a';deep[1]=1;num=0;dfs(1);init();while(q--){_cin(p),_cin(h);///scanf("%d%d",&p,&h);if(deep[p]>h||pre[h].size()==0) printf("Yes\n");else{l=0,r=pre[h].size()-1,pl=-1;while(l<=r){m=(l+r)/2;if(mp1[pre[h][m]]<mp1[p]) l=m+1;else r=m-1,pl=m;}l=0,r=pre[h].size()-1,pr=-1;while(l<=r){m=(l+r)/2;if(mp1[pre[h][m]]>mp2[p]) r=m-1;else l=m+1,pr=m;}if(pl==-1||pl>pr) printf("Yes\n");else{cnt=0;if(pl==0){for(i=0;i<26;i++) if(sum[h][pr].gou[i]) cnt++;}else{for(i=0;i<26;i++) if((sum[h][pl-1].gou[i])^(sum[h][pr].gou[i])) cnt++;}if(cnt<=1) printf("Yes\n");else printf("No\n");}}}return 0;
}/*
6 2
1 1 1 3 3
zacccd
3 1
5 2
*/

 

这篇关于树上的回文 51Nod - 1513的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---