自动搬运

查看原文

来自洛谷，原作者为

	liangbowen 不能再摆了，，，

搬运于2025-08-24 22:14:34，当前版本为作者最后更新于2023-07-13 10:09:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

problem & blog。

题解代码都长得离谱，2k 代码了解一下！

如果我码风比较压行还可以 2k 以内，但是很不幸我是空格 + 大括号换行流。

不妨设 $a \le b \le c$，如果能使 $C$ 联通，那么从中取出一个 $A$ 或 $B$ 的连通块也是平凡的，所以只考虑 $A,B$。

考虑树的情况。要找到一条边 $(u,v)$ 满足 $u$ 那边的子树的 $siz\ge a$，$v$ 那边的子树的 $siz \ge b$。

容易发现 $a\le b\le \dfrac n2$，联想到重心，它的性质是 $\forall siz\le \dfrac n2$，所以只需要枚举与重心相连的边，如果能找到一个子树把 $A$ 塞进去，那么 $n-siz>n-\dfrac n2>\dfrac n2$，很容易就能把 $B$ 塞进去。找不到就是无解。

回到简单图。上面的 Special Task 提示我们建 $\text{DFS}$ 树，并找到它的重心。下文令 $siz_i$ 表示重心相邻的那些点的子树。

如果 $\exists siz_i \ge a$，直接按照树的方法构造即可。否则，考虑第一个子树，有一些其他的子树会与它相连。如果这些相连的子树都算上了，还是没法干掉 $A$，那么必须动用两次重心了，无解。

令 $S$ 表示干掉 $A$ 需要用到的点集。可以认为这个过程是一个一个看子树，当 $\sum\limits_S siz_i$ 成功干掉 $A$，立刻终止。由于 $\forall siz_i < a$，故 $\sum\limits_S siz_i < 2a$。继续化简，$n=a+b+c>2a+b>\sum\limits_S siz_i +b$，所以 $b<n-\sum\limits_S siz_i$，也就是说必定可以干掉 $B$。

输出即可。注意调换了 $a,b,c$ 满足 $a\le b\le c$ 后，输出也要调整一下。

代码，时间复杂度 $O(n+m)$。