L番目の数字
题意翻译
## 题目描述
给出一个图。
- 有$N$个节点,这些节点的编号从$1$到$N$。
- 这些节点通过$N-1$个边缘以树形连接。
- 每个节点$v$都有一个权值$a_v$。
接下来,给出如下格式的$Q$个查询。每个查询$q$,$v_q$,$w_q$和$l_q$。请在所有从节点$v_q$到节点$w_q$的路径中找到节点的第$l_q$个最小值。
- 路径不会两次通过同一顶点。
- 该路径包括两个端点(即顶点$v_q$,$w_q$)。
## 输入格式
第一行包含两个整数$N$和$Q$。
接下来$N$行给出每个点具有的权值。每行一个整数$x_v$表示节点$v$的权值。
接下来$N-1$行给出路径信息。第$e$行包含两个整数$a_e$和$b_e$,它们表示连通的两个节点。
下面的$Q$行代表查询信息。第$q$行包含三个整数$v_q$,$w_q$和$l_q$,它们代表查询$q$的信息。
## 输出格式
输出由$Q$行组成,第$q$行输出查询$q$的答案。
## 数据范围
$1 ≤ N,Q ≤ 10^5$
$1 ≤ x_v ≤ 10^9$
$1 ≤ a_e, b_e ≤ N$
$1 ≤ v_q, w_q ≤ N$
从节点$v_q$到节点$w_q$的路径中至少经过$l_q$个节点。
## 输入输出样例
### 输入 #1
```
6 11
2
4
5
8
9
7
1 3
2 3
3 4
4 5
4 6
1 6 1
1 6 2
1 6 3
1 6 4
1 2 1
1 2 2
1 2 3
2 5 1
2 5 2
2 5 3
2 5 4
```
### 输出 #1
```
2
5
7
8
2
4
5
4
5
8
9
```
题目描述
[problemUrl]: https://atcoder.jp/contests/utpc2011/tasks/utpc2011_12