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

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 có dạng: ai là người sếp chung thấp nhất của nhân viên \(a\) và \(b\) 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,\dots,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 \(a\) và \(b\) ứng với câu hỏi: "Ai là chủ chung thấp nhất của nhân viên \(a\) và \(b\)?"

Output

  • In câu trả lời cho mỗi truy vấn.

Constraints

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

Example

Sample Input

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

Sample Output

3
1
1

Bình luận


  • 0
    N7hoatt    11:44 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 chung của nhân viên \(a\) và \(b\) có bậc thấp nhất trong hệ thống cấp 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 \(a\) và \(b\): tìm người sếp chung của nhân viên \(a\) và \(b\) có bậc thấp nhất trong hệ thống cấp bậc.

    Output

    • In ra kết quả cho \(q\) truy vấn.

    Constraints

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

    Example

    Test

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