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

Xem PDF
Tác giả:
Flower_On_Stone , Elektrikar
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

5
1 2
2 3
3 4
3 5

Sample Output
3

Bình luận


  • -1
    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
    1 phản hồi