P5811 题解

· · 题解

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)。