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ập độc lập trọng số lớn nhất trên cây

    Cho một cây nnn đỉnh, đỉnh iii có trọng số wiw_iwi​. Hãy chọn một tập độc lập (không có hai đỉnh kề nhau cùng được chọn) sao cho tổng trọng số lớn nhất. In ra tổng đó.

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

      Dòng đầu: nnn. Dòng hai: nnn trọng số w1…wnw_1\dots w_nw1​…wn​. n−1n-1n−1 dòng sau: mỗi dòng hai số uuu, vvv 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, 0≤wi≤1090 \le w_i \le 10^90≤wi​≤109.

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

      Một số nguyên: tổng trọng số lớn nhất của tập độc lập.

    Ví dụ:

    Đầu vào:

    5
3 2 1 10 1
1 2
1 3
2 4
2 5

    Đầu ra:

    14

    Giải thích:

    Chọn đỉnh 1 (3), 4 (10), 5 (1) — không kề nhau (4,5 kề 2 chứ không kề nhau) tổng 14; mọi lựa chọn khác nhỏ hơn.

    Đang tải editor...