K-th nhỏ nhất trong cây con
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho cây gốc $1$ có $n$ đỉnh, đỉnh $i$ có giá trị $a_i$. Mỗi truy vấn $(u,k)$ yêu cầu tìm giá trị nhỏ thứ $k$ trong tập giá trị các đỉnh thuộc cây con của $u$ (tính cả $u$).
Dữ liệu vào
Dòng đầu: $n,q$. Dòng hai: $n-1$ số $p_2,\dots,p_n$ (cha của đỉnh $i$, $p_i<i$; dòng này bỏ trống nếu $n=1$). Dòng tiếp theo: $n$ số $a_i$. Sau đó $q$ dòng: $u,k$ với $1\le k\le$ kích thước cây con của $u$.
Dữ liệu ra
Với mỗi truy vấn in đáp án.
Ví dụ
Input
5 5
1 2 2 3
7 -8 -5 -8 -6
3 1
1 5
5 1
1 1
3 1
Output
-6
7
-6
-8
-6
Giới hạn
- $1\le n,q\le 10^5$; $|a_i|\le 10^9$.
- Thời gian: 2 giây; bộ nhớ: 256 MB.
Community Discussion