Đếm trên cây (Count on a tree)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một cây $N$ đỉnh đánh số từ $1$ đến $N$, mỗi đỉnh có một trọng số nguyên. Mỗi truy vấn $u,v,k$ yêu cầu tìm trọng số nhỏ thứ $k$ trên đường đi đơn từ $u$ đến $v$, tính cả hai đầu mút.

Dữ liệu vào

Dòng đầu chứa $N,M$. Dòng thứ hai chứa $N$ trọng số. Tiếp theo là $N-1$ cạnh của cây. Cuối cùng là $M$ dòng truy vấn $u,v,k$.

Kết quả

Với mỗi truy vấn, in trọng số nhỏ thứ $k$ trên đường $u-v$.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, số truy vấn $\le 3000$.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le N,M\le10^5$
• các trọng số là số nguyên
• $1\le u,v\le N$
• $1\le k\le$ số đỉnh trên đường đi từ $u$ tới $v$

Ví dụ

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

Giải thích

Đường từ đỉnh 2 đến 5 đi qua 2-1-3-5, có các trọng số [2,105,9,8]. Sau sắp xếp ta được [2,8,9,105], nên bốn truy vấn đầu lần lượt trả 2,8,9,105.