COT - Count on a tree
题意翻译
# 本题必须使用 C++98 提交
给你一棵有n个结点的树,节点编号为1~n。
每个节点都有一个权值。
要求执行以下操作:
U V K:求从节点u到节点v的第k小权值。
# 输入输出格式
## 输入格式
第一行有两个整数n和m(n,m≤100000)
第二行有n个整数。
第i个整数表示第i个节点的权值。
接下来的n-1行中,每行包含两个整数u v,表示u和v之间有一条边。
接下来的m行,每行包含三个整数U V K,进行一次操作。
## 输出格式
对于每个操作,输出结果。
题目描述
You are given a tree with **N** nodes. The tree nodes are numbered from **1** to **N**. Each node has an integer weight.
We will ask you to perform the following operation:
- **u v k** : ask for the kth minimum weight on the path from node **u** to node **v**
输入输出格式
输入格式
In the first line there are two integers **N** and **M**. (**N, M** <= 100000)
In the second line there are **N** integers. The ith integer denotes the weight of the ith node.
In the next **N-1** lines, each line contains two integers **u** **v**, which describes an edge (**u**, **v**).
In the next **M** lines, each line contains three integers **u** **v** **k**, which means an operation asking for the kth minimum weight on the path from node **u** to node **v**.
输出格式
For each operation, print its result.
输入输出样例
输入样例 #1
8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2
输出样例 #1
2
8
9
105
7