COT - Trọng số lớn thứ k


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.