Cây con gốc v
Đề bài
Mô tả
Cho một cây có gốc là đỉnh , gồm đỉnh, đỉnh mang giá trị . Có truy vấn, truy vấn thứ cho một cặp số nguyên và yêu cầu: duyệt toàn bộ cây con gốc , thu thập giá trị của các đỉnh thuộc cây con gốc vào một mảng, sắp xếp thành dãy không giảm, rồi lấy phần tử ở vị trí thứ trong dãy đó.
Dữ liệu vào
- Dòng chứa số nguyên dương ().
- Dòng chứa số nguyên dương ().
- Dòng chứa số nguyên , với là cha của đỉnh ().
- Dòng tiếp theo chứa số nguyên dương là số lượng truy vấn ().
- dòng sau đó, mỗi dòng chứa hai số nguyên dương và tương ứng với một truy vấn ().
Dữ liệu ra
Với mỗi truy vấn, in ra trên một dòng giá trị tìm được, hoặc nếu cây con gốc có ít hơn đỉnh.
Ràng buộc
Subtasks
- Subtask 1 ( số điểm): .
- Subtask 2 ( số điểm): .
- Subtask 3 ( số điểm): Không có ràng buộc gì thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 5 5 5 7 9 10 1 1 2 2 3 4 1 1 1 2 3 3 2 2 |
5 5 -1 7 |
Truy vấn : cây con gốc cho dãy , phần tử thứ là . Truy vấn : cây con gốc chỉ có đỉnh nên in . Truy vấn : dãy là , phần tử thứ là . |
| 5 4 8 1 6 3 3 1 3 2 5 3 2 1 5 2 1 4 1 5 2 |
3 8 3 6 -1 |
Ví dụ thêm (không có trong đề gốc). Cây con gốc gồm các đỉnh với dãy , phần tử thứ là . Chỉ số đỉnh cha có thể lớn hơn chỉ số đỉnh con. |
Bình luận