Truy Vấn Cây Con Thứ K

Buổi 31 — Policy-Based DS
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho một cây có gốc tại đỉnh $1$ gồm $N$ đỉnh. Mỗi đỉnh $u$ mang một giá trị nguyên $A_u$. Có $Q$ truy vấn, mỗi truy vấn gồm cặp $(u, k)$ yêu cầu tìm giá trị nhỏ thứ $k$ (tính cả các giá trị bằng nhau, đánh số từ $1$) trong cây con gốc $u$. Nếu cây con gốc $u$ có ít hơn $k$ đỉnh, in -1.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $A_1, \dots, A_N$ ($-10^9 \le A_i \le 10^9$).
  • $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh nối của cây.
  • $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, k$ ($1 \le u \le N, 1 \le k \le N$).
Dữ liệu ra
  • Với mỗi truy vấn, in ra kết quả trên một dòng.
Ví dụ
Input Output
5 3
10 5 20 1 15
1 2
1 3
2 4
2 5
1 3
2 2
3 1
10
5
20
Giới hạn
  • $1 \le N, Q \le 10^5$
Draft saved