51nod1513

时间:2021-12-19 22:23:31

题解:

更据题意,在树上深度为没一个数的都放在一起,要用的时候二分出来,看结果

用c++的数据结构

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+,L=;
char s[N];
int n,m,cnt=,max_h=,high[N];
vector<int>E[N],A[N],B[N];
pair<int,int>order[N];
void dfs(int x,int h)
{
max_h=max(h,max_h);
high[x]=h;
order[x].first=++cnt;
A[h].push_back(<<(s[x-]-'a'));
B[h].push_back(cnt);
for (int i=;i<E[x].size();i++)dfs(E[x][i],h+);
order[x].second=cnt;
}
int solve(int x,int h)
{
if (h<=high[x]||!B[h].size())return ;
int l=(int)(lower_bound(B[h].begin(),B[h].end(),
order[x].first)-B[h].begin());
int r=(int)(upper_bound(B[h].begin(),B[h].end(),
order[x].second)-B[h].begin()-);
if (l>r)return ;
int ans=A[h][r]^(l?A[h][l-]:);
if (ans==(ans&(-ans)))return ;
return ;
}
int read()
{
char c=;int x=;
for(;c<''||c>'';c=getchar());
for(;c>=''&&c<='';c=getchar())x=x*+c-'';
return x;
}
int main()
{
n=read();m=read();
for (int i=;i<=n;i++)E[read()].push_back(i);
scanf("%s",&s);
dfs(,);
max_h++;
for (int i=;i<max_h;i++)
for (int j=;j<A[i].size();j++)A[i][j]^=A[i][j-];
while (m--)
{
int v=read(),h=read();
if (solve(v,h-))puts("Yes");
else puts("No");
}
}

相关文章