trang chủ / đề bài / lc_tst_26_e

Cây con gốc v

Đề bài

Mô tả

Cho một cây có gốc là đỉnh 1, gồm n đỉnh, đỉnh i mang giá trị w[i]. Có Q truy vấn, truy vấn thứ i cho một cặp số nguyên (v,k) và yêu cầu: duyệt toàn bộ cây con gốc v, thu thập giá trị w[i] của các đỉnh thuộc cây con gốc v 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ứ k trong dãy đó.

Dữ liệu vào

  • Dòng 1 chứa số nguyên dương n (n≤2·105).
  • Dòng 2 chứa n số nguyên dương w[1],w[2],…,w[n] (|w[i]|≤109).
  • Dòng 3 chứa n−1 số nguyên p[2],p[3],…,p[n], với p[i] là cha của đỉnh i (2≤i≤n).
  • Dòng tiếp theo chứa số nguyên dương Q là số lượng truy vấn (Q≤2·105).
  • Q dòng sau đó, mỗi dòng chứa hai số nguyên dương v và k tương ứng với một truy vấn (1≤v,k≤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 −1 nếu cây con gốc v có ít hơn k đỉnh.

Ràng buộc

  • 1≤n,Q≤2·105
  • 1≤w[i]≤109
  • 1≤v,k≤n

Subtasks

  • Subtask 1 (30% số điểm): n,Q≤600.
  • Subtask 2 (20% số điểm): n,Q≤3000.
  • Subtask 3 (50% 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 (1,1): cây con gốc 1 cho dãy {5,5,5,7,9,10}, phần tử thứ 1 là 5. Truy vấn (3,3): cây con gốc 3 chỉ có 2 đỉnh nên in −1. Truy vấn (2,2): dãy là {5,7,9}, phần tử thứ 2 là 7.
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 3 gồm các đỉnh 3,2,4,5 với dãy {1,3,6,8}, phần tử thứ 2 là 3. Chỉ số đỉnh cha có thể lớn hơn chỉ số đỉnh con.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0