Tìm trọng tâm cây

Đ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

Cho một cây gồm $n$ đỉnh. Hãy tìm một trọng tâm của cây — một đỉnh mà khi xóa đỉnh đó, mọi thành phần liên thông còn lại đều có không quá $⌊ n / 2 ⌋$ đỉnh.

Nếu có nhiều trọng tâm hợp lệ, in ra bất kỳ một đỉnh nào cũng được chấp nhận.

Dữ liệu vào

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

$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ mô tả một cạnh của cây.

Dữ liệu ra

In ra một số nguyên là đỉnh trọng tâm.

Ràng buộc

$1 \leq n \leq 2 \cdot 10^{5}$
$1 \leq a, b \leq n$

Ví dụ

Input	Output	Giải thích
5 1 2 2 3 3 4 3 5	3	Khi xóa đỉnh 3: các thành phần là {4}, {5}, {1,2} — đều có kích thước ≤ 2 = ⌊5/2⌋.
4 1 2 2 3 3 4	2	Khi xóa đỉnh 2: các thành phần là {1}, {3,4} — đều ≤ 2 = ⌊4/2⌋.

Bình luận

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