Chuồng Trại Mới

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Có $Q$ truy vấn được thực hiện theo thứ tự. Mỗi truy vấn thuộc một trong hai loại:

B p: Thêm một đỉnh mới vào đồ thị. Nếu $p \neq - 1$ , nối đỉnh mới này với đỉnh $p$ bằng một cạnh vô hướng. Ngược lại ( $p = - 1$ ), đỉnh mới không kết nối với đỉnh nào. Các đỉnh được đánh số từ $1$ theo thứ tự thêm vào.
Q k: Truy vấn khoảng cách lớn nhất từ đỉnh $k$ đến bất kỳ đỉnh nào đã được thêm vào và có thể đến được từ $k$ .

Đồ thị luôn là một rừng (tập hợp các cây không kết nối với nhau). Với mỗi truy vấn loại Q, in ra khoảng cách lớn nhất tương ứng.

Dòng đầu tiên: số nguyên $Q$ .
Q dòng tiếp theo, mỗi dòng là một truy vấn:
- B p — thêm đỉnh mới, kết nối với đỉnh $p$ (hoặc $p = - 1$ nếu không kết nối).
- Q k — truy vấn khoảng cách xa nhất từ đỉnh $k$ .

Với mỗi truy vấn loại Q, in ra một số nguyên trên một dòng — khoảng cách lớn nhất từ đỉnh $k$ đến bất kỳ đỉnh nào có thể đến được.

Input	Output	Giải thích
7 B -1 Q 1 B 1 B 2 Q 3 B 2 Q 2	0 2 1	Sau `B -1`: đỉnh 1 đứng độc lập. `Q 1` → 0. Sau `B 1`, `B 2`: đỉnh 3 nối vào 1, đỉnh 4 nối vào 2 (chuỗi 3-1-2-4 — nhưng thực ra 2 nối vào 1, 4 nối vào 2, tạo cây 3-1-2-4). `Q 3`: xa nhất là đỉnh 4, khoảng cách 2. `B 2`: thêm đỉnh 5 nối vào đỉnh 2. `Q 2`: xa nhất là đỉnh 3 hoặc 5, khoảng cách 1.

Một đỉnh đứng độc lập (không kết nối đỉnh nào) có khoảng cách xa nhất là $0$ .
Truy vấn Q k chỉ xét các đỉnh đã được thêm vào tính đến thời điểm truy vấn.

Bình luận

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