首页 > 代码库 > codeforces 570 D Tree Requests

codeforces 570 D Tree Requests

题意:给出一棵树。每一个结点都有一个字母,有非常多次询问,每次询问。以结点v为根的子树中高度为h的后代是否可以经过调整变成一个回文串。


做法:
推断能否够构成一个回文串的话,仅仅须要知道是否有大于一个的奇数数目的字母就可以。为了非常快的訪问到一个区间。记录前缀和就可以。为了省内存,状压奇偶就可以。


为了非常快的找到以结点v为根的子树中高度为h的后代,须要dfs整棵树。然后记录每一个结点第一次訪问它的时间戳以及离开它的时间戳,就能够二分出来。




为了省内存,能够离线处理询问。

#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
int head[500010],tail;
struct Edge
{
	int to,next;
}edge[500010];
void add(int from,int to)
{
	edge[tail].to=to;
	edge[tail].next=head[from];
	head[from]=tail++;
}
int in[500010],ot[500010];
int cnt;
struct node
{
	int id,tm;
	node(){}
	node(int id,int tm)
	{
		this->id=id;
		this->tm=tm;
	}
	bool operator <(node a)const
	{
		return tm<a.tm;
	}
};
vector<node>bx[500010];
void dfs(int from,int step)
{
	in[from]=++cnt;
	bx[step].push_back(node(from,cnt));
	for(int i=head[from];i!=-1;i=edge[i].next)
	{
		int to=edge[i].to;
		dfs(to,step+1);
	}
	ot[from]=++cnt;
}
bool num[500010][26];
char s[500010];
void create(int h)
{
	int n=bx[h].size();
	for(int i=0;i<n;i++)
	{
		if(i==0)
		{
			for(int j=0;j<26;j++)
				num[i][j]=0;
		}
		else
		{
			for(int j=0;j<26;j++)
				num[i][j]=num[i-1][j];
		}
		int id=bx[h][i].id-1;
		num[i][s[id]-‘a‘]^=1;
	}
}
bool work(int v,int h)
{
	if(bx[h].empty())
		return 1;
	int l=upper_bound(bx[h].begin(),bx[h].end(),node(-1,in[v]))-bx[h].begin();
	if(l==bx[h].size()||bx[h][l].tm>ot[v])
		return 1;
	int r=lower_bound(bx[h].begin(),bx[h].end(),node(-1,ot[v]))-bx[h].begin();
	l--;r--;
	bool flag=0;
	for(int i=0;i<26;i++)
	{
		bool t;
		if(l<0)
			t=num[r][i];
		else
			t=(num[l][i]^num[r][i]);
		if(t&1)
		{
			if(flag)
				return 0;
			flag=1;
		}
	}
	return 1;
}
struct Q
{
	int id,v,h;
	bool operator <(Q a)const
	{
		return h<a.h;
	}
}q[500010];
bool ans[500010];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof(head));
	for(int i=2;i<=n;i++)
	{
		int p;
		scanf("%d",&p);
		add(p,i);
	}
	scanf("%s",s);
	dfs(1,1);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&q[i].v,&q[i].h);
		q[i].id=i;
	}
	sort(q,q+m);
	int p=-1;
	for(int i=0;i<m;i++)
	{
		if(q[i].h!=p)
		{
			p=q[i].h;
			create(p);
		}
		ans[q[i].id]=work(q[i].v,q[i].h);
	}
	for(int i=0;i<m;i++)
		if(ans[i])
			puts("Yes");
		else
			puts("No");
}


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 then?-?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 the i-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).

Sample test(s)
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".




codeforces 570 D Tree Requests