trang chủ / đề bài / armycmd

Truyền lệnh trong quân đội

Đề bài

Mô tả

Quân đội Berland có n sĩ quan được đánh số từ 1 đến n. Sĩ quan 1 là tổng chỉ huy và không có cấp trên. Mỗi sĩ quan còn lại có đúng một cấp trên trực tiếp. Cấu trúc này tạo thành một cây có gốc tại đỉnh 1.

Khi sĩ quan u phát đi một mệnh lệnh, mệnh lệnh lan truyền theo đúng thứ tự của một lần duyệt DFS bắt đầu từ u: sĩ quan a đang giữ mệnh lệnh sẽ chọn cấp dưới trực tiếp có chỉ số nhỏ nhất trong số những người chưa nhận được lệnh, truyền lệnh cho người đó, rồi chờ cho tới khi người đó truyền xong toàn bộ cấp dưới của mình mới chọn người tiếp theo. Khi không còn cấp dưới trực tiếp nào chưa nhận lệnh, sĩ quan a kết thúc.

Ví dụ, với cây có p2,…,p9=1 1 1 3 5 3 5 7, nếu sĩ quan 1 phát lệnh thì thứ tự nhận lệnh là [1,2,3,5,6,8,7,9,4]; nếu sĩ quan 3 phát lệnh thì thứ tự là [3,5,6,8,7,9].

Cho q truy vấn, truy vấn thứ i gồm cặp (ui,ki). Với mỗi truy vấn, hãy dựng dãy thứ tự nhận lệnh khi sĩ quan ui phát lệnh và in ra phần tử thứ ki của dãy đó, hoặc −1 nếu dãy có ít hơn ki phần tử.

Các truy vấn độc lập với nhau: truy vấn này không ảnh hưởng tới truy vấn khác.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên n và q: số sĩ quan và số truy vấn.
  • Dòng thứ hai chứa n−1 số nguyên p2,p3,…,pn, trong đó pi là chỉ số cấp trên trực tiếp của sĩ quan i.
  • q dòng tiếp theo, dòng thứ i chứa hai số nguyên ui và ki.

Dữ liệu ra

In ra q dòng, dòng thứ i là đáp án của truy vấn thứ i.

Ràng buộc

  • 2≤n≤2·105
  • 1≤q≤2·105
  • 1≤pi<i
  • 1≤ui,ki≤n

Ví dụ

Input Output Giải thích
9 6
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9		 3
6
8
-1
9
4		 Từ 1 thứ tự là [1,2,3,5,6,8,7,9,4] nên phần tử thứ 5 là 6, thứ 8 là 9, thứ 9 là 4. Từ 3 thứ tự là [3,5,6,8,7,9], phần tử thứ 1 là 3 và thứ 4 là 8. Từ 7 chỉ có [7,9], không có phần tử thứ 3 nên in −1.
6 5
1 1 2 2 3
1 4
2 3
3 2
2 4
6 1		 5
5
6
-1
6		 Từ 1 thứ tự là [1,2,4,5,3,6] nên phần tử thứ 4 là 5. Từ 2 thứ tự là [2,4,5]: phần tử thứ 3 là 5, còn thứ 4 không tồn tại. Từ 3 thứ tự là [3,6] nên phần tử thứ 2 là 6. Sĩ quan 6 không có cấp dưới nên dãy chỉ gồm chính nó.

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