Informatica Online Judge

  Tree palindrome [1533 / 05FD]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 12   Total Tried : 14


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[Codeforces]

Background

경곽이는 n개의 노드를 가지는 트리를 만들었다.

이 트리는 다음 성질들을 만족한다.

- 각 노드는 1부터 n까지 번호를 가진다. (1번 노드가 전체 루트이다.)
- 각 노드는 알파벳 소문자를 하나씩 값으로 가지고 있다.
- 번호가 x인 노드 부모노드의 번호를 P_x라 하면, 다음 항상 다음이 성립한다. ( x > P_x, x != 1)
- Dx는 노드 x의 깊이라고 할 때, 1번 노드의 깊이는 1이고, 1을 제외한 다른 노드의 깊이는 Dx = D_(P_x) + 1을 만족한다.

이러한 트리에서 어떤 노드 x를 루트로하는 서브트리에 대해서 다음과 같은 쿼리들을 해결하고자 한다.

쿼리는 다음 결정문제이다.

"x를 루트로하는 서브트리의 노드들 중 깊이가 d인 모든 노드들이 가지는 알파벳들을 적당히 재배치해서 팰린드롬(회문)을 만들 수 있는가?"
(이 때, 깊이 d는 전체 트리에서의 깊이이다.)

이 쿼리를 해결하는 프로그램을 작성하시오.

Input

첫 번째 줄에 노드의 수를 나타내는 정수 n과 쿼리의 수를 나타내는 정수 m이 공백으로 구분되어 입력된다.

두 번째 줄에는 n-1개의 정수가 입력된다. 이 값은 2부터 n번까지의 부모노드의 번호를 나타낸다.

세 번째 줄에는 길이가 n인 문자열이 입력된다. 이 문자열은 각 1번 노드부터 n번 노드까지가 가지는 소문자 알파벳 값을 의미한다.

네 번째 줄부터 m줄에 걸쳐서 쿼리가 입력된다.

각 i번째 쿼리의 값은 x_i, d_i이고, 이는 서브트리의 루트와 전체 트리의 깊이를 나타낸다.

[입력값의 정의역]
1 <= n, m <= 200,000

Output

각 쿼리에 대해서 팰린드롬을 만들 수 있으면 Yes, 아니면 No를 출력한다.

IO Example

입력
6 5
1 1 1 3 3
zacccd
1 1
3 3
4 1
6 1
1 2

출력
Yes
No
Yes
Yes
Yes

* 설명 : 문자가 하나도 없을 경우에도 문자가 없는 팰린드롬으로 취급한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]