Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

CF1336A Linova and Kingdom 解题报告

CF1336A/CF1337C

有一个有 $n$ 个点的树,以 1 为根,你可以选择 $k$ 个节点,使得这 $k$ 个节点到 1 节点的最短路径中经过的非选择的点最多。

思路:

先约定:
$siz_v$ 为以 $v$ 为根的子树大小,当 $v$ 为叶子节点时,$siz_v = 1$。。
$dep_v$ 为从根到 $v$ 的最短路径长度(即深度)。

首先我们可以发现,这里每选择一个点是会对它的子树造成影响。
例如这里:

如果我们已经选择了 4,5,那么如果再选择 2, 4,5 到根节点的权值就会各 -1。
所以我们不止要简单的计算深度最大的,而且要计算它的子树大小最小的。
因此,我们设一个点的贡献为 $f_v$,$f_v = dep_v - siz_v$,最后对 $f_i$ 排序求出最小的 $k$ 个值相加即可。
显然对于 $dep_i$ 和 $siz_i$ 我们可以通过一遍 DFS 求出来

1
2
3
4
5
6
7
8
9
void dfs1(int s,int f) {
a[s].dep = a[f].dep+1,a[s].siz = 1;
for (int i = hd[s];i;i = nxt[i]) {
int v = to[i];
if (v == f) continue;
dfs1(v,s);
a[s].siz += a[v].siz;
}
}

之后就是简单的计算 $f_i$ 的过程了,不再多说。

代码

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
//本代码是赛时代码,可能有些变量名称不一样,但大体思路一致。
#include <bits/stdc++.h>
using namespace std;
#define int long long//答案会超出int的范围
#define ri register int

inline int read() {
char v = getchar();int x = 0,f = 1;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {x = x * 10 + v - 48;v = getchar();}
return x * f;
}

const int N = 500001;
const int M = 500001;

int to[M],hd[N],nxt[M],tot;

inline void add(int u,int v) {to[++tot] = v;nxt[tot] = hd[u];hd[u] = tot;}
inline void addedge(int u,int v) {add(u,v),add(v,u);}

struct node {
int dep,siz;
}a[N];
//a[i].dep 存的是 dep[i] a[i].siz 存的是 siz[i]
inline bool cmp(node a,node b) {
return (a.dep-a.siz)>(b.dep-b.siz);
}
//按照dep[i] - siz[i](也就是f[i])排序
void dfs1(int s,int f) {
a[s].dep = a[f].dep+1,a[s].siz = 1;//计算dep和siz
for (int i = hd[s];i;i = nxt[i]) {
int v = to[i];
if (v == f) continue;
dfs1(v,s);
a[s].siz += a[v].siz;
}
}

int n,k,ans;

signed main() {
n = read(),k = read();
for (int i = 1;i < n;++i) {
int x = read(),y = read();
addedge(x,y);
}
a[0].dep = 0,a[0].siz = 0;
dfs1(1,0);
sort(a+1,a+1+n,cmp);//排序
for (int i = 1;i <= k;++i) {
ans += (a[i].dep - a[i].siz);
}//选前k个
cout << ans;
return 0;
}