【2022 NOIP 模拟赛 8】C. 退休计划 II 做题记录

给定 $N$ 个点和 $M$ 条边的连通图，求一条简单路径 $path$ 和两个点集 $s1$ 和 $s2$，满足：

• $|s1| = |s2|$，两个点集大小相同（可以为空）；
• $|s1| + |s2| + |path| = N$ 且 $s1 \cap s2 = \varnothing$ 且 $s1 \cap path = \varnothing$ 且 $s2 \cap path = \varnothing$，即两个点集和简单路径恰好覆盖了所有点；
• $s1$ 和 $s2$ 之间没有边直接相连。

或者宣称这样的方案不存在。

$1\le N,M\le 2\times 10^5$

一眼 dfs 树，然后考虑在树上构造。

根本不会无解。

显然根节点 $rt$ 一定要让公主占领，然后若根节点 $rt$ 的儿子的子树恰好可以分给两个王子使得满足条件，那么公主选根节点，根节点的儿子子树平均分给两个王子就行。

否则考虑递归构造，设当前两个王子分别占领了 $sum0$ 个点和 $sum1$ 个点，那么不难想到一个策略：

• 先让公主占领 $rt$；
• 遍历 $rt$ 除重儿子 $hson$ 之外的儿子 $v$，若 $sum0<sum1$，那么 $v$ 的子树分配给第一个王子，否则分配给第二个王子；
• 若分配完之后 $|sum0-sum1|=siz_{hson}$ 那么构造完成，否则此时一定有 $|sum0-sum1|<siz_{hson}$，那么递归构造 $hson$ 的子树。