Thành phố Surabaya có \(N\) nút giao thông, được đánh số từ \(0\) đến \(N - 1\). Các nút giao thông được nối với nhau bởi \(N - 1\) con đường hai chiều, được đánh số từ \(0\) đến \(N - 2\), sao cho có đúng một đường đi giữa hai nút giao thông bất kỳ qua các con đường này. Con đường \(i\) (\(0 \le i \le N - 2\)) nối nút giao thông \(U[i]\) và \(V[i]\).

Để nâng cao nhận thức về môi trường, Pak Dengklek, với vai trò là thị trưởng thành phố Surabaya, dự định tổ chức một Ngày Không Ô tô. Để khuyến khích sự kiện này, Pak Dengklek sẽ tổ chức đóng đường. Đầu tiên, Pak Dengklek chọn một số nguyên không âm \(k\), sau đó đóng một số con đường sao cho mỗi nút giao thông được nối trực tiếp với không quá \(k\) con đường chưa bị đóng. Chi phí để đóng con đường \(i\) là \(W[i]\).

Hãy giúp Pak Dengklek tìm tổng chi phí nhỏ nhất để đóng đường cho mỗi số nguyên không âm \(k\) có thể có (\(0 \le k \le N - 1\)).

Chi tiết cài đặt

Thí sinh cần cài đặt hàm sau:

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W);

• \(N\): số lượng nút giao thông của thành phố Surabaya.
• \(U\) và \(V\): hai mảng độ dài \(N - 1\), trong đó nút giao thông \(U[i]\) và \(V[i]\) được nối với nhau bởi con đường \(i\).
• \(W\): mảng độ dài \(N - 1\), trong đó \(W[i]\) là chi phí để đóng con đường \(i\).
• Hàm phải trả về đúng một mảng độ dài \(N\). Với mỗi \(k\) (\(0 \le k \le N - 1\)), phần tử thứ \(k\) là tổng chi phí nhỏ nhất để đóng đường sao cho mỗi nút giao thông được nối trực tiếp với không quá \(k\) con đường chưa bị đóng.
• Hàm được gọi đúng một lần.

Ví dụ

Ví dụ 1

Xét lời gọi sau:

minimum_closure_costs(5, {0, 0, 0, 2}, {1, 2, 3, 4}, {1, 4, 3, 2});

Lời gọi này biểu diễn \(5\) nút giao thông và \(4\) con đường nối các cặp nút giao thông \((0, 1)\), \((0, 2)\), \((0, 3)\) và \((2, 4)\), với chi phí đóng đường lần lượt là \(1\), \(4\), \(3\) và \(2\).

{{asset:apio21roads/roads-1.png}}

Để đạt được chi phí nhỏ nhất:

• Nếu Pak Dengklek chọn \(k = 0\), tất cả các con đường phải bị đóng, với tổng chi phí \(1 + 4 + 3 + 2 = 10\).
• Nếu Pak Dengklek chọn \(k = 1\), con đường \(0\) và con đường \(1\) phải bị đóng, với tổng chi phí \(1 + 4 = 5\).
• Nếu Pak Dengklek chọn \(k = 2\), con đường \(0\) phải bị đóng, với tổng chi phí \(1\).
• Nếu Pak Dengklek chọn \(k = 3\) hoặc \(k = 4\), không cần đóng con đường nào.

Vì vậy, hàm minimum_closure_costs phải trả về \([10, 5, 1, 0, 0]\).

Ví dụ 2

Xét lời gọi sau:

minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5});

Lời gọi này biểu diễn \(4\) nút giao thông và \(3\) con đường nối các cặp nút giao thông \((0, 1)\), \((2, 0)\) và \((0, 3)\), với chi phí đóng đường lần lượt là \(5\), \(10\) và \(5\).

{{asset:apio21roads/roads-2.png}}

Để đạt được chi phí nhỏ nhất:

• Nếu Pak Dengklek chọn \(k = 0\), tất cả các con đường phải bị đóng, với tổng chi phí \(5 + 10 + 5 = 20\).
• Nếu Pak Dengklek chọn \(k = 1\), con đường \(0\) và con đường \(2\) phải bị đóng, với tổng chi phí \(5 + 5 = 10\).
• Nếu Pak Dengklek chọn \(k = 2\), con đường \(0\) hoặc con đường \(2\) phải bị đóng, với tổng chi phí \(5\).
• Nếu Pak Dengklek chọn \(k = 3\), không cần đóng con đường nào.

Vì vậy, hàm minimum_closure_costs phải trả về \([20, 10, 5, 0]\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(0 \le U[i], V[i] \le N - 1\) với mọi \(0 \le i \le N - 2\).
• Có thể di chuyển giữa mọi cặp nút giao thông qua các con đường này.
• \(1 \le W[i] \le 10^9\) với mọi \(0 \le i \le N - 2\).

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng \(1\): \(N\).
• Dòng \(2 + i\) (\(0 \le i \le N - 2\)): \(U[i]\ V[i]\ W[i]\).

Trình chấm mẫu ghi ra một dòng duy nhất chứa mảng do hàm minimum_closure_costs trả về.

5
0 1 1
0 2 4
0 3 3
2 4 2

10 5 1 0 0

4
0 1 5
2 0 10
0 3 5

20 10 5 0

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2021: Road Closures.