Informatica Online Judge

  돌연변이 [2368 / 0940]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 2   Total Tried : 3


The Champion of this Problem (C++) : gs18080 - ms / 2554byte
My Best Submission (C++) : N/A

[36th 이민규(gs18080)]
Writer ID : [gs18080]

Background

생물학 전공인 지민이는 어느날 새로운 바이러스를 발견하였다. 이 바이러스는 굉장히 빠른 속도로 여러 개의 자식 바이러스를 만들어낸다. 처음에는 한개의 바이러스만이 존재했고, 자식 바이러스가 만들어지는 과정을 트리로 나타낼 수 있다. 트리의 모든 바이러스는 숫자로 구분지을 수 있으며 태초의 바이러스는 1번 바이러스이다.

또한 각각의 바이러스는 돌연변이율 pi 을 가지고 있다. 지민이는 임의의 x번째 바이러스를 골라서, 그 바이러스의 k대손들 중 최대 돌연변이율을 구하고 싶어졌다. 그리곤 갑자기 옆에 있던 민규에게 이러한 q개의 질문을 하기 시작했다. 민규를 도와주자.

Input

첫 번째 줄에 바이러스의 개수 n 과 지민이의 질문의 개수 q 가 주어진다.

그 다음 줄에는 1부터 n까지 각각의 바이러스의 돌연변이율 pi (1 ≤ pi ≤ 10^8)가 공백으로 구분되어 주어진다. 그 다음 줄에는 2번부터 n번 바이러스의 부모 바이러스가 한 줄에 공백으로 구분되어 주어진다.

마지막 q개의 줄에는 지민이의 질문을 나타내는 두 개의 정수 x (1 ≤ x ≤ n), k (0 ≤ k ≤ n) 가 공백으로 구분되어 주어진다.

입력으로 주어지는 값의 범위는 아래와 같다

1 ≤ n ≤ 2×10^5 , 1 ≤ q ≤ 2×10^5

Output

q개의 질문에 대한 답을 한 줄에 하나씩 출력한다.
x번째 바이러스의 k대손들 중 최대 돌연변이율을 출력하면 된다.
만약 x번째 바이러스의 k대손이 존재하지 않는다면 -1을 출력한다.

IO Example

입력 예제
3 3
1 2 3
1 1
1 0
1 1
1 2

출력 예제
1
3
-1

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

출력2
3
7
5
7

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