Đ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
5
1 2
2 3
3 4
3 5
Sample Output
3
Bình luận
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
Output
Constraints
Example
Test
Input
Output
Note