CSES - Finding a Centroid | Tìm một Trọng tâm

Tác giả:

Dạng bài

Điểm: 1600 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một cây \(n\) nút, nhiệm vụ của bạn là tìm một trọng tâm, tức là một nút sao cho khi nó làm gốc của cây, mỗi cây con có nhiều nhất \(⌊n/2⌋\) nút.

Input

Dòng đầu tiên là một số nguyên \(n\) : số nút. Các nút được đánh số \(1,2,…, n\).
Tiếp theo là \(n−1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b:\) có một cạnh nối hai nút \(a\) và \(b\).

Output

In ra một số nguyên: một nút trọng tâm. Nếu có nhiều đáp án, bạn có thể chọn bất kỳ đáp án nào.

Constraints

\(1 \le n \le 2 \cdot 10^5\)
\(1 \le a,b \le n\)

Example

Sample Input

Sample Output

Bình luận

-6
N7hoatt 5:32 p.m. 29 Tháng 8, 2023
Cho một cây gồm \(n\) đỉnh. Hãy xác định trọng tâm của cây. Trọng tâm của một cây là một đỉnh khi nó làm gốc của cây thì mỗi cây con có nhiều nhất \(⌊n/2⌋\) đỉnh.

Input

Dòng đầu tiên gồm số nguyên \(n\): số lượng đỉnh. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).

\(n-1\) dòng sau đó biểu diễn các cạnh. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có cạnh nối giữa \(a\) và \(b\).

Output

In ra một số nguyên: trọng tâm của cây. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Constraints

\(1\leq n\leq 2 \times 10^5\).

\(1\leq a,b\leq n\).

Example

Test

Input

5 1 2 2 3 3 4 3 5

Output

3

Note
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
2 phản hồi