问题分析

给定一棵包含 $N$ 个节点的树，每条边有一个关闭代价 $W[i]$。对于每个 $k$（$0 \le k \le N-1$），我们需要找到关闭一些边的最小总代价，使得每个节点的度数不超过 $k$。

关键思路

这个问题可以转化为：对于每个 $k$，找到最小代价的边集，使得删除这些边后，每个节点的度数不超过 $k$。

核心观察

度数限制：当 $k$ 增加时，限制变松，需要关闭的边数减少

树结构：在树中，度数限制问题可以通过树形 DP 解决

单调性：随着 $k$ 增大，答案单调递减

算法设计

主要步骤

1.预处理：

计算每个节点的度数

按度数降序排序节点

对每个节点的邻接表按邻居度数降序排序

2.按 $k$ 值处理：

对于每个 $k$，只考虑度数大于 $k$ 的节点（度数小的节点自然满足条件）

使用树形 DP 计算最小关闭代价

3.动态规划状态：

$f[u][0]$：不关闭 $u$ 到父节点边时的最小代价

$f[u][1]$：关闭 $u$ 到父节点边时的最小代价

数据结构优化

使用优先队列（堆）来维护每个节点的决策：

维护可能被关闭的边的代价

当需要限制度数时，选择代价最小的边进行保留

复杂度分析

时间复杂度：$O(N \log N)$，每个边最多被处理一次

空间复杂度：$O(N)$

代码实现要点

// 主要数据结构
struct pq {
    priority_queue<ll> s;  // 大根堆，存储边代价
    ll sum;                // 堆中所有元素的和
    
    void push(ll x);       // 插入元素
    void limit(int x);     // 限制堆大小为 x
    void pop();            // 弹出最大元素
};

// 树形 DP
void dfs(int u, int pre) {
    // 处理子树，计算 f[u][0] 和 f[u][1]
    // 考虑是否关闭 u 到父节点的边
}

样例验证

对于样例：

$k = 0$：关闭所有边，代价 $1+4+3+2=10$

$k = 1$：关闭代价为 $1$ 和 $4$ 的边，总代价 $5$

$k = 2$：关闭代价为 $1$ 的边，总代价 $1$

$k \ge 3$：不需要关闭任何边，代价 $0$

输出结果：$[10, 5, 1, 0, 0]$，与预期一致。

总结

该算法通过结合树形 DP 和堆优化，高效地解决了度数限制下的最小关闭代价问题。通过按度数排序和增量处理，避免了重复计算，达到了较好的时间复杂度。

AC代码

#include <bits/stdc++.h>
#include "roads.h"
#define rep(i, j, k) for(int i=(j); i<=(k); ++i)
#define per(i, j, k) for(int i=(j); i>=(k); --i)
#define aprint(a, len) cout<<#a<<"="; rep(i, 0, len-1) cout<<(a)[i]<<' '; cout<<endl
using namespace std;
namespace DEBUG {
template<class T> void _debug(const char *s, T x) {
    cout << s << '=' << x << endl;
}
template<class F, class... Nxt> void _debug(const char *s, F x, Nxt... nxt) {
    int d = 0;

    while (*s != ',' || d)
        d += *s == '(', d -= *s == ')', cout << *s++;

    cout << '=' << x << ',';
    _debug(s + 1, nxt...);
}
template<class T> ostream &operator<<(ostream &c, vector<T> v) {
    c << '[';

    for (auto x : v)
        c << x << ", ";

    return c << ']';
}
#define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__)
} using namespace DEBUG;
using vi = vector<int>;
using ll = long long;
using pa = pair<int, int>;
#define siz(x) (int)x.size()
const int N = 1e5 + 3;
const ll inf = 1e18;
int n, d[N], k;
vector<pa> G[N];
vi id;
ll f[N][2];
bool vis[N];
struct pq {
    priority_queue<ll> s;
    ll sum;
    void push(ll x) {
        s.emplace(x);
        sum += x;
    }
    void limit(int x) {
        while (siz(s) > x)
            sum -= s.top(), s.pop();
    }
    void pop() {
        sum -= s.top();
        s.pop();
    }
} q[N];
void cmin(ll &a, ll b) {
    a = a < b ? a : b;
}

void dfs(int u, int pre) {
    q[u].limit(d[u] - k);
    vis[u] = 1;
    vector<ll> z;
    ll sum = 0;

    for (auto [v, w] : G[u])
        if (v != pre) {
            if (d[v] <= k)
                break;

            dfs(v, u);
            sum += f[v][0];
            z.emplace_back(f[v][1] + w - f[v][0]);
        }

    sort(z.begin(), z.end());
    rep(del, 0, 1) {
        if (del && !pre)
            continue;

        vector<ll> tmp;
        int d =::d[u] - del - k, c = q[u].s.size();
        ll s = sum;
        f[u][del] = inf;

        if (c > d && siz(q[u].s))
            tmp.emplace_back(q[u].s.top()), q[u].pop(), --c;

        if (c >= d)
            cmin(f[u][del], s + q[u].sum);

        for (auto x : z) {
            ++c, s += x;

            if (c > d && siz(q[u].s))
                tmp.emplace_back(q[u].s.top()), q[u].pop(), --c;

            if (c >= d)
                cmin(f[u][del], s + q[u].sum);
        }

        for (auto x : tmp)
            q[u].push(x);
    }
}

vector<ll> minimum_closure_costs(int N, vi U, vi V, vi W) {
    n = N;
    rep(i, 0, n - 2) {
        int u = U[i] + 1, v = V[i] + 1, w = W[i];
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
        ++d[u], ++d[v];
    }
    rep(i, 1, n) id.emplace_back(i);
    sort(id.begin(), id.end(), [&](int x, int y) {
        return d[x] > d[y];
    });
    rep(i, 1, n) sort(G[i].begin(), G[i].end(), [&](pa x, pa y) {
        return d[x.first] > d[y.first];
    });
    vector<ll> ans;

    for (k = 0; k <= n - 1; k++) {
        while (siz(id) && d[id.back()] <= k) {
            int u = id.back();

            for (auto [v, w] : G[u])
                q[v].push(w);

            id.pop_back();
        }

        ll res = 0;

        for (auto x : id)
            if (!vis[x]) {
                dfs(x, 0);
                res += f[x][0];
            }

        ans.emplace_back(res);

        for (auto x : id)
            vis[x] = 0;
    }

    return ans;
}