首页 > 代码库 > codeforces 570D.Tree Requests
codeforces 570D.Tree Requests
[题目大意]：
给定一棵树，树的每个节点对应一个小写字母字符，有m个询问，每次询问以vi为根节点的子树中，深度为hi的所有节点对应的字符能否组成一个回文串；
[题目分析]：
先画个图，可看出每次询问的所有节点都是一个从1开始bfs遍历完成的节点序列中的一段，已知深度hi的情况下，可以二分得到深度为hi的那一段的位置；
那么如何满足找到的节点必须在以vi为根的子树内这个条件？
可以想到dfs的时间戳，把1-n的数组按深度排序，深度相同的按照dfs时间戳排序；
这样就可以二分得到要求的所有节点的位置；
这样可以O（n）
分析回文串可知，如果奇数数量的字符不超过1个，那么一定能组成回文串；
用前缀和xor优化；
可以做到O(nlogn);
#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>#include<algorithm>#include<iomanip>#include<map>#include<set>#include<vector>#include<ctime>#include<cmath>using namespace std;#define LL long long#define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)#define max(x,y) ((x)<(y)?(y):(x))#define min(x,y) ((x)<(y)?(x):(y))#define FILE "1"#define pii pair<int,int>const int maxn=503000,inf=1000000000;int read(){ int x=0;bool flag=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)flag=1;ch=getchar();} while(ch<=‘9‘&&ch>=‘0‘){x=x*10+ch-‘0‘;ch=getchar();} return flag?-x:x;}struct node{ int y,next;}e[maxn<<1];int n,m;int linkk[maxn],len=0,sum[maxn];int dfs_clock=0,fa[maxn];char s[maxn];int f[maxn];struct Node{ int dep,pre,lat,id; bool operator<(const Node &b)const{return dep<b.dep||(dep==b.dep&&pre<b.pre);}}a[maxn];void insert(int x,int y){ e[++len].y=y; e[len].next=linkk[x]; linkk[x]=len;}void dfs(int x){ a[x].pre=++dfs_clock;a[x].id=x; for(int i=linkk[x];i;i=e[i].next){ if(e[i].y==fa[x])continue; a[e[i].y].dep=a[x].dep+1; dfs(e[i].y); } a[x].lat=++dfs_clock;}void init(){ n=read(),m=read();int x; up(i,2,n){ x=read(); insert(i,x); insert(x,i); fa[i]=x; } scanf("%s",s+1); a[1].dep=1; dfs(1); sort(a+1,a+n+1); for(int i=1;i<=n;i++)f[a[i].id]=i;}int find(int x,int Dep){ int left=1,right=n,mid; int L=0,R=0; while(left<=right){ mid=(left+right)>>1; if(a[mid].dep<Dep)left=mid+1; else { right=mid-1; if(a[mid].dep==Dep)L=mid; } } left=1,right=n,mid=0; while(left<=right){ mid=(left+right)>>1; if(a[mid].dep<=Dep){ left=mid+1; if(a[mid].dep==Dep)R=mid; } else right=mid-1; } if(!L&&!R)return 1; left=L,right=R; int u=0,v=0; while(left<=right){ mid=(left+right)>>1; if(a[mid].pre>=a[f[x]].pre){ right=mid-1; if(a[mid].pre>=a[f[x]].pre&&a[mid].pre<=a[f[x]].lat)u=mid; } else left=mid+1; } left=L,right=R; while(left<=right){ mid=(left+right)>>1; if(a[mid].pre<=a[f[x]].lat){ left=mid+1; if(a[mid].pre>=a[f[x]].pre&&a[mid].pre<=a[f[x]].lat)v=mid; } else right=mid-1; } if(!u||!v)return 1; int p=sum[v]^sum[u-1]; int cnt=0; while(p){ if(p&1)cnt++; p>>=1; } if(cnt>=2)return 0; else return 1;}void work(){ int x,y; for(int i=1;i<=n;i++)sum[i]=sum[i-1]^(1<<(s[a[i].id]-‘a‘)); while(m--){ x=read(),y=read(); if(find(x,y))printf("Yes\n"); else printf("No\n"); }}int main(){ init(); work(); return 0;}
codeforces 570D.Tree Requests
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。