Truy vấn tổ tiên thứ k

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Một công ty có $n$ nhân viên, đánh số từ $1$ đến $n$ . Nhân viên số $1$ là tổng giám đốc. Mỗi nhân viên từ $2$ đến $n$ có đúng một người quản lý trực tiếp $e_{i}$ (với $e_{i} < i$ ).

Trả lời $q$ truy vấn: với mỗi truy vấn $(x, k)$ , hãy tìm người quản lý ở cách nhân viên $x$ đúng $k$ cấp trên trong hệ thống cấp bậc. Nếu không tồn tại, in $- 1$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$ .

Dòng thứ hai chứa $n - 1$ số nguyên $e_{2}, e_{3}, \dots, e_{n}$ : người quản lý trực tiếp của mỗi nhân viên.

$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $k$ .

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên.

Ràng buộc

$1 \leq n, q \leq 2 \cdot 10^{5}$
$1 \leq e_{i} \leq i - 1$
$1 \leq x \leq n$
$1 \leq k \leq n$

Ví dụ

Input	Output	Giải thích
5 3 1 1 3 3 4 1 4 2 4 3	3 1 -1	Nhân viên 4 có quản lý trực tiếp là 3. 2 cấp trên là 1. Không có 3 cấp trên.
4 2 1 2 3 4 3 1 1	1 1	Chuỗi 1←2←3←4. 3 cấp trên của 4 là 1. 1 cấp trên của 1 không tồn tại... nhưng 1 cấp trên của đỉnh 1 là -1.

Bình luận

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