Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Tìm trọng tâm của cây

    Cho cây nnn đỉnh. Trọng tâm (centroid) là đỉnh mà khi xóa nó đi, thành phần liên thông lớn nhất còn lại có kích thước ≤⌊n/2⌋\le \lfloor n/2 \rfloor≤⌊n/2⌋. Một cây có 1 hoặc 2 trọng tâm; nếu có hai, hãy in chỉ số nhỏ hơn.

    • Định dạng đầu vào:

      Dòng đầu: nnn. n−1n-1n−1 dòng sau: các cạnh uuu, vvv.

    • Ràng buộc đầu vào:

      1≤n≤2⋅1051 \le n \le 2\cdot10^51≤n≤2⋅105.

    • Định dạng đầu ra:

      Một số nguyên: chỉ số trọng tâm (nhỏ hơn nếu có hai).

    Ví dụ:

    Đầu vào:

    4
1 2
2 3
3 4

    Đầu ra:

    2

    Giải thích:

    Đường thẳng 1-2-3-4 (n=4). Xóa đỉnh 2: phần lớn nhất {3,4} cỡ 2 = ⌊4/2⌋. Đỉnh 3 cũng thỏa; in chỉ số nhỏ hơn là 2.

    Đang tải editor...