0%

[CF1336A] Linova and Kingdom

题目

题目链接

题目大意:给出一个 $n$ 个点的有根树,每个城市可以有两种类型 A 和 B,每个 A 城市的幸福度定义为从 A 到根的最短路径上 B 城市的个数,最大化所有 A 城市的幸福度之和。$1 \le n \le 2 \times 10^5$。

思路

有一个很显然的贪心思路,每次一定要取离树根最远的点,考虑预处理到根的距离。

但是这样有一个问题,如果这个点的父亲结点也被选上了,那么这个点的幸福度会减少。

发现可以如果选了一个父亲结点,那么总幸福度减少了这个点的子树大小,dfs 的时候减一下就行了。

注意开 long long。

代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return;
}

typedef long long LL;

std::vector<int> g[200010];
LL siz[200010], dis[200010];
LL n, k, ans;

void dfs(int now, int pa) {
siz[now] = 1;
for (auto i : g[now]) {
if (i ^ pa) {
dis[i] = dis[now] + 1;
dfs(i, now);
siz[now] += siz[i];
}
}
dis[now] -= siz[now] - 1;
}

int main() {
read(n), read(k);
for (int i = 1, u, v; i < n; ++i) {
read(u), read(v);
g[u].push_back(v), g[v].push_back(u);
}
dfs(1, 0);
std::sort(dis + 1, dis + n + 1, [](LL a, LL b) {
return a > b;
});
for (int i = 1; i <= k; ++i) ans += dis[i];
printf("%lld\n", ans);
return 0;
}