Truy Vấn Cây Con Thứ K
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề 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$
Community Discussion