11932번 - 트리와 K번째 수

문제

1번부터 N번까지 번호가 붙여진 N개의 정점과 N-1개의 간선으로 구성된 트리가 있다. 트리의 각 정점에는 가중치가 있다. 이때 M개의 질문에 대해 다음의 연산을 수행해야 한다.

연산 X Y K : 정점 X와 Y를 잇는 경로 상에서 K번째로 작은 가중치를 출력한다.

입력

첫째 줄에는 두 개의 양의 정수 N과 M이 주어진다. (1 ≤ N, M ≤ 100,000)

둘째 줄에는 각 정점의 가중치를 나타내는 N개의 정수가 주어진다. i번째 정수는 i번 정점의 가중치이다. 이 가중치는 모두 서로 다른 값들이며 int 범위이다.

다음 N-1개의 각 줄에는 트리의 간선 (X, Y)를 나타내는 두 정수 X와 Y가 주어진다.

다음 M개의 각 줄에는 연산을 나타내는 세 양의 정수 X Y K가 주어진다. X, Y는 1 이상이고 N 이하이다. K는 1 이상이고 X와 Y를 잇는 경로 상의 정점의 개수 이하이다. X와 Y가 같다면, 경로 상의 정점의 개수는 1개라 간주한다.

출력

M개의 줄에 걸쳐서 각 연산에 해당하는 답을 출력한다.

제한

힌트