Top Cluster

Top Cluster는 트리 위의 데이터를 관리하는 데 유용한 자료 구조이다. Top Cluster를 쓰면 구간 질의를 효율적으로 처리할 수 있다.

자료 구조 기술을 매우 좋아하는 EMmm은 지금 Top Cluster를 공부하고 있고, 어떤 자료 구조 문제를 풀려고 한다. EMmm과 함께 이 문제를 풀 프로그램을 작성해 보자.

이 문제에서는 정점이 $n$개인 트리가 주어진다. 정점에는 $1, 2, \ldots, n$의 번호가 붙어 있다. $i$번 정점의 값은 음이 아닌 정수 $w_i$이다. 모든 값은 서로 다르다.

이어서 $q$개의 질의가 주어진다. $i$번째 질의에서는 두 정수 $x_i$와 $k_i$($1 \leq x_i \leq n$, $0 \leq k_i \leq 10^{15}$)가 주어지고, $\mathrm{mex}\left(\{w_u \mid \mathrm{dist}(u, x_i) \leq k_i \land 1 \leq u \leq n\}\right)$의 값을 구해야 한다.

여기서 $\mathrm{dist}(u, v)$는 정점 $u$에서 정점 $v$까지 가는 최단 경로의 길이이다. 수학에서 집합의 mex(minimum excluded value)는 집합에 속하지 않는 가장 작은 음이 아닌 정수이다.

EMmm은 mex 문제를 잘 푼다. 모든 값이 서로 다를 때, 위 문제는 주어진 범위 밖에서 나타났거나 트리 전체에서 한 번도 나타나지 않은 가장 작은 음이 아닌 정수를 찾는 문제와 같다는 것을 알아냈다. 여기서 범위 밖이란 $\mathrm{dist}(x_i, u) > k_i$인 경우를 말한다. 그녀는 여기서 더 나아가지 못한다. 그녀를 도와줄 수 있는가?

첫째 줄에 정점의 개수 $n$과 질의의 개수 $q$가 주어진다($1 \leq n, q \leq 5 \cdot 10^5$).

둘째 줄에 정점의 값 $w_1, w_2, \ldots, w_n$이 주어진다($0 \leq w_i \leq 10^9$). 모든 값은 서로 다르다.

다음 $n-1$개의 줄에는 세 정수 $u_i$, $v_i$, $\ell_i$가 주어진다. 이는 정점 $u_i$와 $v_i$를 잇는 길이 $\ell_i$의 양방향 간선을 뜻한다($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq \ell_i \leq 10^9$). 입력은 트리이다.

다음 $q$개의 줄에는 각 질의의 $x_i$와 $k_i$가 주어진다($1 \leq x_i \leq n$, $0 \leq k_i \leq 10^{15}$).

각 질의에 대해 구한 mex 값을 한 줄에 하나씩 출력한다.