CSES - Company Queries I | Truy vấn công ty I

Xem PDF
Tác giả:
Flower_On_Stone , haidanghutcansa , An09855
Dạng bài
Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một công ty có \(n\) nhân viên, tạo thành một hệ thống phân cấp dạng cây trong đó mỗi nhân viên, ngoại trừ tổng giám đốc đều có một ông chủ.

Nhiệm vụ của bạn là xử lý \(q\) truy vấn dưới dạng: ai là người sếp cao hơn nhân viên \(x\) \(k\) bậc trong hệ thống phân cấp?

Input

  • Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q:\) số lượng nhân viên và truy vấn. Các nhân viên được đánh số \(1,2,... ,n\) và người số \(1\) là tổng giám đốc.
  • Dòng tiếp theo có \(n−1\) số nguyên \(e_{2},e_{3},... ,e_{n}:\) người chủ mỗi nhân viên \(2,3,... ,n\).
  • Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên \(x\) và \(k\) ứng với câu hỏi: "Ai là người sếp cao hơn nhân viên \(x\) \(k\) bậc?"

Output

  • In câu trả lời cho mỗi truy vấn. Nếu không tồn tại một ông chủ như vậy , hãy in −1.

Constraints

  • \(1 ≤ n,q ≤ 2⋅10^5\)
  • \(1 ≤ e_{i} ≤ i − 1\)
  • \(1 ≤ x ≤ n\)
  • \(1 ≤ k ≤ n\)

Example

Sample Input

5 3
1 1 3 3
4 1
4 2
4 3

Sample Output

3
1
-1

Bình luận


  • 0
    N7hoatt    11:39 a.m. 17 Tháng 8, 2023

    Một công ty có \(n\) nhân viên, tạo thành một hệ thống cấp bậc dạng cây, trong đó mỗi nhân viên đều có một sếp, ngoại trừ tổng giám đốc.

    Hãy thực hiện \(q\) truy vấn có dạng: tìm người sếp trên nhân viên \(x\) \(k\) bậc.

    Input

    • Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\) lần lượt là số nhân viên và số truy vấn. Các nhân viên được đánh số từ \(1,2,3,\dots,n\) và nhân viên \(1\) là tổng giám đốc.
    • Dòng tiếp theo gồm \(n-1\) số nguyền \(e_2,e_3,\dots,e_n\): sếp của mỗi nhân viên \(2,3,\dots,n\).
    • \(q\) dòng cuối cùng biểu diễn các truy vấn. mỗi dòng gồm hai số nguyên \(x\) và \(k\): tìm người sếp trên nhân viên \(x\) \(k\) bậc.

    Output

    • In ra kết quả cho \(q\) truy vấn. In ra \(-1\) nếu không tồn tại người sếp thõa mãn.

    Constraints

    • \(1\leq n,q\leq 2 \times 10^5\).
    • \(1\leq e_i\leq i - 1\).
    • \(1\leq x,k\leq n\).

    Example

    Test

    Input 
    5 3
1 1 3 3
4 1
4 2
4 3
    Output 
    3
1
-1
    Note