시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 594 | 259 | 193 | 43.468% |
N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 정점은 가중치를 가지고 있다.
아래의 쿼리를 수행하는 프로그램을 작성하시오.
u v k
: u에서 v로 가는 경로에 존재하는 정점의 가중치 중에서 k번째 작은 가중치를 출력한다.첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.
둘째 줄에는 정점의 가중치가 1번 정점부터 순서대로 주어진다.
셋째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v가 주어진다.
다음 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.
다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.
정점의 가중치는 항상 1,000,000보다 작거나 같은 자연수이다.
각각의 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.
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