Codeforces Round #316 (Div. 2) D. Tree Requests dfs序

D. Tree Requests
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Roman planted a tree consisting of n vertices. Each vertex contains a lowercase English letter. Vertex 1 is the root of the tree, each of the n - 1 remaining vertices has a parent in the tree. Vertex is connected with its parent by an edge. The parent of vertex i is vertex pi, the parent index is always less than the index of the vertex (i.e., pi < i).

The depth of the vertex is the number of nodes on the path from the root to v along the edges. In particular, the depth of the root is equal to 1.

We say that vertex u is in the subtree of vertex v, if we can get from u to v, moving from the vertex to the parent. In particular, vertex v is in its subtree.

Roma gives you m queries, the i-th of which consists of two numbers vihi. Let's consider the vertices in the subtree vi located at depthhi. Determine whether you can use the letters written at these vertices to make a string that is a palindrome. The letters that are written in the vertexes, can be rearranged in any order to make a palindrome, but all letters should be used.

Input

The first line contains two integers nm (1 ≤ n, m ≤ 500 000) — the number of nodes in the tree and queries, respectively.

The following line contains n - 1 integers p2, p3, ..., pn — the parents of vertices from the second to the n-th (1 ≤ pi < i).

The next line contains n lowercase English letters, the i-th of these letters is written on vertex i.

Next m lines describe the queries, the i-th line contains two numbers vihi (1 ≤ vi, hi ≤ n) — the vertex and the depth that appear in thei-th query.

Output

Print m lines. In the i-th line print "Yes" (without the quotes), if in the i-th query you can make a palindrome from the letters written on the vertices, otherwise print "No" (without the quotes).

Examples
input
6 5
1 1 1 3 3
zacccd
1 1
3 3
4 1
6 1
1 2
output
Yes
No
Yes
Yes
Yes
Note

String s is a palindrome if reads the same from left to right and from right to left. In particular, an empty string is a palindrome.

Clarification for the sample test.

In the first query there exists only a vertex 1 satisfying all the conditions, we can form a palindrome "z".

In the second query vertices 5 and 6 satisfy condititions, they contain letters "с" and "d" respectively. It is impossible to form a palindrome of them.

In the third query there exist no vertices at depth 1 and in subtree of 4. We may form an empty palindrome.

In the fourth query there exist no vertices in subtree of 6 at depth 1. We may form an empty palindrome.

In the fifth query there vertices 2, 3 and 4 satisfying all conditions above, they contain letters "a", "c" and "c". We may form a palindrome "cac".

题意:给你一棵树,n个节点,m个询问;根节点为1;根结点的深度为1,

    每个节点含有一个权值;

    询问给你一个节点node,以node为根的子树中深度为x的结点,能否形成回文串;

思路:首先,能行成回文,只需要奇数的字母个数<=1;状态压缩标记即可;

   然后处理这课树,dfs序形成一个序列处理;

   对于m个询问, 两种思路:

   1:打表每个字母+深度进行存in[i](vector),然后m个询问复杂度o(26*(m*log(n));

   2:可以再广搜一遍,对于深度相同的必然是连续的一段序列,利用前缀异或和处理,复杂度(m*log(n));

   

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
const int N=5e5+,M=1e6+,inf=1e9+;
const ll INF=1e18+,mod=;
int in[N],out[N],tot,a[N],flag[N],deep[N];
struct is
{
int v,nex;
}edge[N<<];
int head[N<<],edg;
int n,p;
void init()
{
memset(head,-,sizeof(head));
memset(a,,sizeof(a));
edg=;
tot=;
}
void add(int u,int v)
{
edg++;
edge[edg].v=v;
edge[edg].nex=head[u];
head[u]=edg;
}
void dfs(int u,int fa,int d)
{
deep[u]=d;
in[u]=++tot;
for(int i=head[u];i!=-;i=edge[i].nex)
{
int v=edge[i].v;
if(v==fa)continue;
dfs(v,u,d+);
}
out[u]=tot;
}
char ch[N];
int root,x;
vector<int>ans[][N];
int main()
{
int n,q;
while(~scanf("%d%d",&n,&q))
{
init();
for(int i=;i<=n;i++)
{
int v;
scanf("%d",&v);
add(i,v);
add(v,i);
}
dfs(,-,);
scanf("%s",ch+);
//for(int i=1;i<=n;i++)
// cout<<in[i]<<" "<<out[i]<<endl;
for(int i=;i<=n;i++)
flag[in[i]]=i;
for(int i=;i<=n;i++)
a[i]=deep[flag[i]];
for(int i=;i<=n;i++)
ans[ch[flag[i]]-'a'][a[i]].push_back(in[flag[i]]);
for(int i=;i<;i++)
{
for(int j=;j<=n;j++)
{
sort(ans[i][j].begin(),ans[i][j].end());
}
}
/*for(int i=0;i<26;i++)
{
for(int j=1;j<=n;j++)
{
cout<<j<<" ";
for(int k=0;k<ans[i][j].size();k++)
cout<<ans[i][j][k]<<" ";
cout<<endl;
}
cout<<"~~~~"<<endl;
}*/
while(q--)
{
scanf("%d%d",&root,&x);
if(deep[root]>=x)
{
printf("Yes\n");
continue;
}
int tot=;
for(int i=;i<;i++)
{
int pos1=lower_bound(ans[i][x].begin(),ans[i][x].end(),in[root])-ans[i][x].begin()-;
int pos2=upper_bound(ans[i][x].begin(),ans[i][x].end(),out[root])-ans[i][x].begin()-;
//cout<<pos1<<" "<<pos2<<endl;
tot+=(pos2-pos1)%;
}
if(tot>=)
printf("No\n");
else
printf("Yes\n");
}
}
return ;
}
上一篇:oracle 11g行转列 列转行


下一篇:codeforces 570 D. Tree Requests (dfs)