Tổ tiên chung thấp nhất (LCA)

Đ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 $(a, b)$ , hãy tìm người quản lý chung thấp nhất (LCA) của hai nhân viên $a$ và $b$ — tức là người quản lý chung ở cấp cao nhất trong hệ thống mà vẫn là cấp trên của cả hai.

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 $a$ và $b$ .

Dữ liệu ra

Với mỗi truy vấn, in ra người quản lý chung thấp nhất của $a$ và $b$ .

Ràng buộc

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

Ví dụ

Input	Output	Giải thích
5 3 1 1 3 3 4 5 2 5 1 4	3 1 1	LCA(4,5) = 3 (cả hai đều dưới nhân viên 3). LCA(2,5) = 1 (tổng giám đốc). LCA(1,4) = 1 (1 là tổ tiên của 4).
3 1 1 1 2 3	1	Cả 2 và 3 đều trực thuộc 1.

Bình luận

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