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 trọng số cây con lớn nhất

    Cho cây có gốc tại đỉnh 111, gồm nnn đỉnh, mỗi đỉnh iii có trọng số wiw_iwi​ (có thể âm). Cây con gốc tại vvv gồm vvv và tất cả con cháu của nó. Định nghĩa T(v)T(v)T(v) là tổng trọng số của mọi đỉnh trong cây con gốc vvv.

    Hãy tìm max⁡vT(v)\max_v T(v)maxv​T(v). Sử dụng quy hoạch động trên cây (subtree DP) duyệt O(n)O(n)O(n).

    Ví dụ: Cây 1 ⁣− ⁣21\!-\!21−2, 1 ⁣− ⁣31\!-\!31−3 với w=[−5,4,4]w=[{-}5, 4, 4]w=[−5,4,4]: T(2)=4T(2)=4T(2)=4, T(3)=4T(3)=4T(3)=4, T(1)=−5+4+4=3T(1)=-5+4+4=3T(1)=−5+4+4=3, đáp án 444.

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

      Dòng đầu chứa nnn. Dòng thứ hai chứa nnn số nguyên w1…wnw_1 \dots w_nw1​…wn​. n−1n-1n−1 dòng tiếp theo, mỗi dòng hai số 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, ∣wi∣≤109|w_i| \le 10^9∣wi​∣≤109.

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

      In ra một số nguyên là tổng trọng số cây con lớn nhất.

    Ví dụ:

    Đầu vào:

    3
-5 4 4
1 2
1 3

    Đầu ra:

    4

    Giải thích:

    Cây con gốc 2 chỉ chứa đỉnh 2, tổng 4; tương tự cây con gốc 3 tổng 4. Cây con gốc 1 chứa cả ba, tổng -5+4+4=3. Lớn nhất là 4.

    Đang tải editor...