CF1120D 题解

本文最后更新于:2023年3月18日 晚上

题面链接

题意

有一棵有根树,根节点编号为11。每个点都有一个权值wiw_i
现在给每个叶子节点一个数cic_i,你可以花费wiw_i购买下ii这个节点,使其子树内的所有叶子节点的值加上一个正数。对于任意的cic_i,求出所有花费最少的能够使所有叶子节点上的数字相同的方案的并集。

分析

首先,很自然的可以想到叶子节点可以按照访问顺序排列,这样每棵子树都是一个区间,子树内的叶子权值都加上一个数就是区间加法。
其次,题目要求我们使得所有的叶子节点上的数相同。我们想,对于一个序列,如果他的每一项都相同,那么他的差分序列就是一段00。那么,在区间[l,r][l,r]上的区间修改,就可以转化为在差分序列上的ll点和r+1r+1两个点的单点修改。
进一步推导,我们可以发现,对于llr+1r+1两个点的单点修改,最少可以把一个点上的数变为00。而想要把n+1n+1个数中的nn[1]都变成00,那么就要选择nn个区间。很显而易见的,这就可以转化成一个最小生成树问题:一个节点xx,对应的边就是(lx,rx+1,wx)(l_x,r_x+1,w_x)。这样,问题就解决了。

代码

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
#define int long long
using namespace std;
int read() {
int x = 0, f = 1;
char c = getchar();
while (c > '9' || c < '0') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + c - '0';
c = getchar();
}
return x * f;
}
const int N = 2E5 + 10;
int n;
int w[N];
// graph
int head[N], to[N << 1], nxt[N << 1], ecnt;
void adde(int a, int b) {
ecnt++;
nxt[ecnt] = head[a];
head[a] = ecnt;
to[ecnt] = b;
}
// DSU
int f[N];
int findf(int x) { return f[x] == 0 ? x : f[x] = findf(f[x]); }
// Kruskal;
int leaves[N], //这个节点子树中的叶子节点个数
id; // 叶子节点个数
bool selected[N];
struct edge {
int from, to, w, v;
} es[N << 1];
int necnt;
void inse(int a, int b, int w, int v) {
necnt++;
es[necnt] = {a, b, w, v};
}
void kruskal() {
sort(es + 1, es + 1 + necnt,
[](const edge &a, const edge &b) { return a.w < b.w; });
int l = 1;
int k = 0;
int mst = 0;
while (l <= n) {
int r;
// 统计重复的边
for (r = l; r <= n; r++) {
if (es[r].w != es[r + 1].w)
break;
}
// 因为要求并集,所以都要选上
for (int i = l; i <= r; i++) {
if (findf(es[i].from) != findf(es[i].to)) {
selected[es[i].v] = 1;
k++;
}
}
// 统计一次边的权值
for (int i = l; i <= r; i++) {
int fu = findf(es[i].from);
int fv = findf(es[i].to);
if (fu == fv)
continue;
mst += es[i].w;
f[fu] = fv;
}
l = r + 1;
}
// 输出
cout << mst << ' ' << k << endl;
for (int i = 1; i <= n; i++) {
if (selected[i])
cout << i << ' ';
}
cout << endl;
}
void dfs1(int x, int fa) {
bool vis = 0; // 有儿子,不是叶子节点
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) {
dfs1(v, x);
vis = 1;
leaves[x] += leaves[v];
}
}
if (!vis) { // 是叶子节点
id++;
leaves[x] = 1;
}
}
void dfs2(int x, int fa, int l) {
// clog << l << "==>" << l + leaves[x] << ", w=" << w[x] << ", node " << x
// << endl;

// 统计子树
inse(l, l + leaves[x], w[x], x);
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) {
dfs2(v, x, l);
l += leaves[v];
}
}
}
signed main() {
n = read();
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
for (int i = 1; i < n; i++) {
int a = read(), b = read();
adde(a, b);
adde(b, a);
}
dfs1(1, 0);
dfs2(1, 0, 1);
kruskal();
return 0;
}

C++
  1. 这是因为差分序列的第一项可以不为00,所以只需要选。

CF1120D 题解
https://blog.decalvin.tk/2022/09/12/CF1120D/
作者
Franz DeCalvin
发布于
2022年9月12日
更新于
2023年3月18日
许可协议