ABC302 Ex 题解

首先我们考虑 \(v\) 固定怎么做。实际上就是 ARC111B。

考虑建图，对每个 \((a_i,b_i)\) 建一条无向边，那么问题就变成了：对于每条边都要选择它以及其连接的一个点，最大化选出的点数。

很明显可以对每个连通块分开考虑。

记当前连通块的点数为 \(V\)，边数为 \(E\)。那么有结论：该连通块对答案的贡献为 \(\min(V,E)\)。

考虑证明。由于是连通块，所以 \(E\) 最小为 \(V-1\)（树）。接下来我们根据 \(V\) 和 \(E\) 的关系分类讨论：

• \(E=V-1\)。此时连通块为一棵树。随便钦定一个点为根，然后每条边选儿子，这样就可以选掉除了根节点外的所有点，答案为 \(V-1=E=\min(V,E)\)。很明显选出来的点数不可能比选的边数还多，所以这是对的。

• \(E\ge V\)。这个时候必然能给每个点都选出一条边，答案为 \(V=\min(V,E)\)。

这样我们就证完了。

具体实现的时候使用并查集，维护连通块内点数、边数，合并时分类讨论即可。

Code

接下来考虑树上的每个点，我们在 DFS 的时候把当前点 \(u\) 加入连通块中并计算答案，搜索完 \(u\) 时再消除 \(u\) 对答案的影响即可。

怎么消除影响？使用可撤销并查集，将每次合并压入栈中，撤销时取出栈中信息并复原即可。

注意此时并查集不能使用路径压缩，因为这样会破坏树的结构。使用启发式合并即可。时间复杂度 \(O(n\log n)\)，可以通过此题。

Code