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ổng khoảng cách lớn nhất trên cây

    Cho một cây gồm nnn đỉnh (đánh số 111 đến nnn) với n−1n-1n−1 cạnh, mỗi cạnh có độ dài 111. Với mỗi đỉnh vvv, định nghĩa S(v)S(v)S(v) là tổng khoảng cách từ vvv tới tất cả các đỉnh khác.

    Hãy tìm giá trị max⁡vS(v)\max_v S(v)maxv​S(v) — tổng khoảng cách lớn nhất. Sử dụng kỹ thuật đổi gốc (rerooting DP) để tính mọi S(v)S(v)S(v) trong O(n)O(n)O(n).

    Ví dụ: Đường thẳng 1 ⁣− ⁣2 ⁣− ⁣31\!-\!2\!-\!31−2−3: S(1)=1+2=3S(1)=1+2=3S(1)=1+2=3, S(2)=1+1=2S(2)=1+1=2S(2)=1+1=2, S(3)=3S(3)=3S(3)=3, nên đáp án là 333.

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

      Dòng đầu chứa nnn. n−1n-1n−1 dòng tiếp theo, mỗi dòng hai số u vu\ vu v là một cạnh.

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

      1≤n≤2⋅1051 \le n \le 2\cdot10^51≤n≤2⋅105, 1≤u,v≤n1 \le u, v \le n1≤u,v≤n.

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

      In ra một số nguyên là tổng khoảng cách lớn nhất.

    Ví dụ:

    Đầu vào:

    3
1 2
2 3

    Đầu ra:

    3

    Giải thích:

    Cây là đường thẳng 1-2-3. S(1)=1+2=3, S(2)=1+1=2, S(3)=2+1=3. Giá trị lớn nhất là 3, đạt tại hai đầu mút.

    Đang tải editor...