2019 ICPC Nanchang Onsite

Problem A

Unsolved.

Problem B

Solved by Kilo_5723. 04:57 (+2)

Problem C

Solved by Weaver_zhu. 01:05 (+)

Problem D

Unsolved.

Problem E

Solved by Xiejiadong. 00:48 (+)

题意：图中有白边和黑边，至多只能选 $k$ 条白边，求使得所有图联通的最大权值。

题解：因为边的权值都是非负的。所以黑边全部连上。

然后要权值最大，所以默认白边权值大的在前，做一次最小生成树，看是否能够用 $\le k$ 条边联通图。

如果不可以或者无法使得图联通，显然无解。

如果还可以继续加白边，肯定根据权值从大到小将未加入的边加入。

Problem F

Unsolved.

Problem G

Solved by Kilo_5723 && Xiejiadong. 01:19 (+)

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by Xiejiadong. 03:03 (+)

题意：求有根树上有多少节点对 $(u,v)$ 满足：

• $u\neq v$ ;
• $z=lca(u,v) 2val_z=val_u+val_v$ ;
• $|path(u,v)| \le k$ .

题解：对于只有前两个限制的问题非常好处理，直接在树上维护每个节点及其孩子的权值，启发式合并的时候，计算贡献即可。

现在又有一个距离的限制 $k$ 。

我们如果对于较小的一个集合枚举每一个元素可能产生的节点对贡献，可以发现，如果我们按照权值为第一关键字、层数为第二关键字排序，可行的一定是连续的一段。

于是考虑用 pbds 维护结点及其孩子的权值以及层数，然后启发式合并即可。

Problem L

Solved by Kilo_5723. 00:25 (+2)

Problem M

Unsolved. (-6)