抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

AutumnKite's Blog

博客

归档

友链

关于

说说

留言

「Codeforces 1119F」Niyaz and Small Degrees

This is a picture without description

AutumnKite
题解Codeforces

发布于：2019年4月21日
次浏览

题目传送门

题意

给定一棵 \(n\) 个节点的树，有边权，对于所有 \(x\ (0\le x < n)\)，可以删去一些边，求使得所有节点的度数 \(\le x\) 的删掉的边的边权之和的最小值。

节点的度数指以该点为某一端点的边的数量。

\(n\le 250\,000\)

暴力——独立求解

显然是树形 DP，记 \(dp_{u,0/1}\) 表示 \(u\) 与父亲的连边不删/删时，以 \(u\) 为根的子树满足所有节点度数 \(\le x\) 的删掉的边的最小值。

不考虑度数限制，显然有 \(dp_{u,0}=dp_{u,1}=\sum \min(dp_{v,0},dp_{v,1}+w)\)（\(v\) 是 \(u\) 的儿子，\(w\) 表示对应边的边权）。记 \(d_i\) 表示 \(i\) 的度数，把 \(dp_{v,1}+w\le dp_{v,0}\) 的儿子 \(v\) 叫做好儿子，其余叫做坏儿子。考虑度数限制，假设求 \(dp_{u,0}\)（\(dp_{u,1}\) 同理），记 \(cnt\) 为好儿子数量，我们需要把 \(\max(0,d_i-x-cnt)\) 个坏儿子变成好儿子。

只需要维护一个堆，将所有坏儿子 \(dp_{v,1}+w-dp_{v,0}\) 的值压入堆中，将前 \(\max(0,d_i-x-cnt)\) 小的值之和记为 \(sum\)，则 \(dp_{u,0}=sum+\sum dp_{v,0}\)。

时间复杂度 \(O(n^2\log n)\)。

暴力代码

注意代码实现与上述有很大差别，但思想一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
int read(){
    register int x = 0;
    register char f = 1, ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = !f;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
    return f ? x : -x;
}
#define N 250005
#define INF 0x3f3f3f3f3f3f3f3fll
int n;
int edge, to[N << 1], pr[N << 1], tw[N << 1], hd[N];
void addedge(int u, int v, int w){
    to[++edge] = v, tw[edge] = w, pr[edge] = hd[u], hd[u] = edge;
}
long long dp[N][2];
void dfs(int X, int u, int fa = 0){
    std :: vector<long long> val;
    dp[u][0] = dp[u][1] = 0;
    for (register int i = hd[u], v; i; i = pr[i])
        if ((v = to[i]) != fa) dfs(X, v, u), val.push_back(dp[v][1] + tw[i] - dp[v][0]), dp[u][0] += dp[v][0];
    dp[u][1] = dp[u][0];
    std :: sort(val.begin(), val.end());
    int d = val.size();
    for (register int i = 0; i < d && (i < d - X || val[i] < 0); ++i) dp[u][1] += val[i];
    if (!X) return dp[u][0] = INF, void(0);
    ++d;
    for (register int i = 0; i < d - 1 && (i < d - X || val[i] < 0); ++i) dp[u][0] += val[i];
}
int main(){
    n = read();
    for (register int i = 1, u, v, w; i < n; ++i)
        u = read(), v = read(), w = read(), addedge(u, v, w), addedge(v, u, w);
    for (register int i = 0; i < n; ++i) dfs(i, 1), printf("%lld ", dp[1][1]);
}

正解

可以发现对于某个 \(x\)，若一个节点 \(u\) 的度数 \(\le x\)，那这个点本身就不需要考虑了，只需要将 \(w(u,v)\) 加入与 \(v\) 的堆中。

也就是说，我们把 \(u\) 当做叶子节点来看待，即：

1
2
3
4
 /\       /\
/__\     /__\
    \   /
      u

也相当于把 \(u\) “删去”，不同的是，与 \(u\) 相连的点的度数不会改变。

如果我们可以每次在把所有度数 \(\le x\) 的点删去后的森林中进行 DP（对每棵树进行 DP 然后把每棵树根节点的 \(dp\) 值加起来，具体是加 \(dp_{i,0}\) 还是 \(dp_{i,1}\) 要看写法），点数之和为 \(\sum_{x=0}^{n-1}\sum_{i=1}^{n} [d_i>x]=\sum_{i=1}^{n} d_i=2n-2=O(n)\)，总时间复杂度就变为 \(O(n\log n)\) 了。

具体实现时，可以用两个普通堆实现一个支持删除的堆。每次“删去”一个点 \(u\) 时，在所有与该点相连的点 \(v\) 对应的堆中加入 \(w(u,v)\)；DP 时，假设需要把 \(cnt\) 个坏儿子变为好儿子，则我们强制使得堆中只有 \(cnt\) 个值，同时记录堆中所有值之和，这样 \(dp\) 值就可以很容易地求出；求出 \(dp\) 值之后，为了避免每次重新执行所有“删点操作”，我们需要将堆中由“删点”得来的值保留，即把强制删去的值重新插入堆中，把 DP 时得来的值从堆中删去。

正解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
int read(){
    register int x = 0;
    register char f = 1, ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = !f;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
    return f ? x : -x;
}
#define N 250005
#define INF 0x3f3f3f3f3f3f3f3fll
int n, d[N], X, vis[N];
long long sum;
std :: vector< std :: pair<int, int> > E[N];
std :: pair<int, int> D[N];
void addedge(int u, int v, int w){
    E[u].push_back(std :: make_pair(v, w)), ++d[u];
}
bool cmp(std :: pair<int, int> x, std :: pair<int, int> y){
    return d[x.first] > d[y.first];
}
struct Normal_Heap{ // 普通大根堆
    std :: vector<long long> a;
    void push(long long x){ a.push_back(x), std :: push_heap(a.begin(), a.end()); }
    long long top(){ return a[0]; }
    void pop(){ std :: pop_heap(a.begin(), a.end()), a.pop_back(); }
    long long popn(){ long long x; return std :: pop_heap(a.begin(), a.end()), x = a[a.size() - 1], a.pop_back(), x; }
    int size(){ return a.size(); }
};
struct Erase_Heap{ // 用两个普通堆实现的支持删除的大根堆
    Normal_Heap a, b;
    int sz; long long sum;
    void push(long long x){ a.push(x), ++sz, sum += x; }
    void erase(long long x){ b.push(x), --sz, sum -= x; }
    void pre(){ while (a.size() && b.size() && a.top() == b.top()) a.pop(), b.pop(); }
    long long top(){ return pre(), a.top(); }
    void pop(){ pre(), --sz, sum -= a.top(), a.pop(); }
    int size(){ return sz; }
}H[N];
void die(int u){ // “删点”操作
    for (auto to : E[u]){
        register int v = to.first, w = to.second;
        if (d[v] <= X) break;
        H[v].push(w);
    }
}
long long dp[N][2];
std :: vector<long long> tmp, del;
void dfs(int u, int fa = 0){
    vis[u] = X;
    int num = d[u] - X;
    long long res = 0;
    for (; H[u].size() > num; H[u].pop()) ;
    for (auto to : E[u]){
        register int v = to.first, w = to.second;
        if (v == fa) continue;
        if (d[v] <= X) break;
        dfs(v, u);
    }
    tmp.clear(), del.clear();
    for (auto to : E[u]){
        register int v = to.first, w = to.second;
        if (v == fa) continue;
        if (d[v] <= X) break;
        long long x = dp[v][1] + w - dp[v][0];
        if (x <= 0){ --num, res += dp[v][1] + w; continue; }
        res += dp[v][0], H[u].push(x), del.push_back(x);
    }
    for (; H[u].size() && H[u].size() > num; H[u].pop()) tmp.push_back(H[u].top()); // 强制弹堆
    dp[u][0] = res + H[u].sum;
    for (; H[u].size() && H[u].size() > num - 1; H[u].pop()) tmp.push_back(H[u].top()); // 强制弹堆
    dp[u][1] = res + H[u].sum;
    for (auto i : tmp) H[u].push(i); // 还原强制弹堆时删除的值
    for (auto i : del) H[u].erase(i); // 删除 DP 得来的值
}
int main(){
    n = read();
    for (register int i = 1, u, v, w; i < n; ++i)
        u = read(), v = read(), w = read(), addedge(u, v, w), addedge(v, u, w), sum += w;
    printf("%lld", sum);
    for (register int i = 1; i <= n; ++i)
        D[i] = std :: make_pair(d[i], i), std :: sort(E[i].begin(), E[i].end(), cmp);
    std :: sort(D + 1, D + 1 + n);
    register int i = 1;
    for (X = 1; X < n; ++X){
        while (i <= n && D[i].first == X) die(D[i].second), ++i;
        long long ans = 0;
        for (register int j = i; j <= n; ++j){
            register int v = D[j].second;
            if (vis[v] == X) continue;
            dfs(v), ans += dp[v][0];
        }
        printf(" %lld", ans);
    }
    putchar('\n');
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://autumnkite.github.io/cf1119f-sol/

更新于：2020年3月26日

堆

树形DP

评论