Informatica Online Judge

  준호는 자료구조 마스터 [2401 / 0961]

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


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

[36th 박준호(gs18050)]
Writer ID : [gs18050]

Background

준호는 최근에 떡상하고 있는 자료구조 마스터이다. 이러한 준호의 소문에 흥미가 생긴 제 2의 투어리스트 은수는 다음과 같은 문제로 준호를 테스트해보려고 한다.

N개의 정점으로 이루어진 트리가 있다. 정점에는 각각 1~N의 번호가 붙어있고, 간선은 1~N-1의 번호가 붙어있다. 정점들은 각각 가중치가 있다.

다음과 같은 쿼리를 수행하는 프로그램을 만들어 준호가 진정한 자료구조 마스터가 될 수 있도록 도와주자.

- x y k : x에서 y로 가는 경로 위의 가중치 중 k번째로 작은 값을 출력한다.

Input

첫째 줄에 N(2<=N<=100,000)이 주어진다.
둘째 줄에는 정점의 가중치가 1번 정점부터 순서대로 주어진다.

셋째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v가 주어진다.

다음 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

정점의 가중치는 항상 1,000,000보다 작거나 같은 자연수이다.

Output

각각의 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.
단, k가 주어진 두 정점 사이의 정점과 두 정점을 합한 개수보다 클 경우 -1을 출력한다.

IO Example

예제 입력

8
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
5
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2

예제 출력

2
8
9
105
7

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