COT - Trọng số lớn thứ k
Cho một cây có $N$ đỉnh được đánh số từ 1 đến $N$. Đỉnh $i$ được gán trọng số $w_i$.
Có $Q$ truy vấn, mỗi truy vấn, hãy tìm trọng số lớn thứ $k$ của các đỉnh trên đường đi từ $u$ đến $v$.
Dữ liệu
- Dòng đầu tiên chứa 2 số nguyên $N, Q \ (1\le N, Q \le 10^5)$;
- Dòng tiếp theo chứa $N$ số nguyên $w_i \ (1\le t_i \le 10^9)$;
- $N-1$ dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương $u, v \ (1\le u,v \le N)$ - mô tả mỗi cạnh trên cây;
- $Q$ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương $u,v,k \ (1\le u,v \le N; 1\le k\le $ số đỉnh trên đường đi từ $u$ đến $v)$.
Kết quả
- In kết quả của mỗi truy vấn trên mỗi dòng.
Ví dụ
Ví dụ 1
input
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
output
2
8
9
105
7
Comments