Coi thành phố như một cây ~n~ đỉnh, ~n-1~ cạnh có gốc là đỉnh ~1~. Nếu xét một tập ~k~ đỉnh, thì cách tính chi phí đi từ đỉnh ~1~ tới tất cả ~k~ đỉnh như sau:

• Gọi ~\text{max_d}~ là đường đi dài nhất từ đỉnh ~1~ xuống một đỉnh thuộc tập;

• Gọi ~\text{sum_d}~ là tổng trọng số các cạnh kết nối giữa đỉnh ~1~ với ~k~ đỉnh được chọn;

• Chi phí là ~2~ ~\times~ ~\text{sum_d}~ ~-~ ~\text{max_d}~.

Từ đó ta rút ra ý tưởng quy hoạch động: gọi ~\text{dp}(u,\text{cnt},\text{max_d})~ = ~\min(\text{sum_d})~ với ý nghĩa:

• Xét cây con gốc ~u~;

• Đã chọn được ~\text{cnt}~ đỉnh;

• ~\text{max_d}~ và ~\text{sum_d}~ có ý nghĩa như trên.

Chuyển trạng thái:

1. Gọi ~\text{dpChild}(i, c, \text{max_d})~ là ~\min(\text{sum_d})~ khi xét ~u~ và ~i~ con đầu của ~u~ và đã chọn ~c~ đỉnh;

2. Ban đầu ~\text{dpChild}(0, 0, 0)~ = ~\text{dpChild}(0, 1, 0)~ = ~0~;

3. Xét con ~v~ thứ ~i~ của ~u~:

   • Giả sử trong cây con gốc ~v~ ta đã chọn được ~c'~ đỉnh và đường đi dài nhất là ~\text{max_v}~;

   • Nếu không chọn đỉnh nào trong gốc ~v~, nghĩa là ~c' = 0~, ta chuyển ~\text{dpChild}(i + 1, c, \text{max_d})~ ~\leftarrow~ ~\text{dpChild}(i, c, \text{max_d})~;

   • Ngược lại, đường đi dài nhất từ một đỉnh ~v~ lên gốc sẽ được cộng thêm ~w~ với ~w~ là trọng số cạnh ~(u, v)~ (vì nó phải đi qua ~u~) và tổng trọng số các cạnh được sử dụng sẽ tăng lên một lượng là ~w + \text{dp}(v, c', \text{max_v})~. Như vậy ta có thể chuyển ~\text{dpChild}(i + 1, c + c',\max(\text{max_d}, \text{max_v} + w))~ ~\leftarrow~ ~\text{dpChild}(i, c, \text{max_d})~ ~+~ ~w~ ~+~ ~\text{dp}(v, c', \text{max_v})~

Độ phức tạp là ~\mathcal{O}(n^4 \times \text{max_d})~ (có ~n \times \text{max_d}~ trạng thái, chuyển mất ~n^2~). Tuy nhiên ta có thể dùng trick giới hạn ~c~ trong các lần chuyển, để độ phức tạp giảm còn ~\mathcal{O}(n^3 \times \text{max_d})~.

Tuy nhiên ta có nhận xét: không nhất thiết ta phải trừ đi ~\text{max_d}~, mà ta có thể trừ đi ~d~ của một đỉnh bất kì (trong đó ~d_u~ là độ sâu của đỉnh ~u~) và lấy min tất cả trường hợp. Bởi vì nếu như ta không trừ đi một giá trị ~d_u~ lớn nhất, thì đáp án sẽ không tối ưu, và ta sẽ không bao giờ ghi nhận nó là kết quả.

Từ đó, hàm quy hoạch động của chúng ta có thể chuyển thành:

~\text{dp}(u,\text{cnt},0/1)~ = ~\min(\text{sum_d})~, với chiều ~0/1~ thể hiện ta đã trừ đi độ sâu của đỉnh nào chưa. Độ phức tạp giảm còn ~\mathcal{O}(n^2)~.

#include <bits/stdc++.h>

using namespace std;

template <class X, class Y>
bool minimize(X &x, const Y &y) {
    return x > y ? x = y, 1 : 0;
}

using ll = long long;

const int N = 5005;

vector<pair<int, int>> adj[N];
ll dp[N][N][2], sum[N];
int sz[N];

void dfs_prep(int u, int p) {
    sz[u] = 1;
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        sum[v] = sum[u] + w;
        dfs_prep(v, u);
    }
}

void dfs_dp(int u, int p) {
    memset(dp[u], 0x3f, sizeof dp[u]);
    sz[u] = 1;
    dp[u][1][0] = dp[u][0][0] = 0;
    dp[u][1][1] = -sum[u];
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        dfs_dp(v, u);
        for (int i = sz[u]; i >= 0; i--) {
            for (int j = 0; j <= sz[v]; j++) {
                int add = 2 * w * (j > 0);
                minimize(dp[u][i + j][0], dp[u][i][0] + dp[v][j][0] + add);
                minimize(dp[u][i + j][1], dp[u][i][0] + dp[v][j][1] + add);
                minimize(dp[u][i + j][1], dp[u][i][1] + dp[v][j][0] + add);
            }
        }
        sz[u] += sz[v];
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    freopen("migration.inp", "r", stdin);
    freopen("migration.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    dfs_prep(1, 0);
    dfs_dp(1, 0);
    for (int i = 1; i <= n; i++) {
        cout << dp[1][i][1] << '\n';
    }
}