题解：P7320 「PMOI-4」可怜的团主

ran_qwq · 2025-07-21 14:11:50 · 题解

类似的题：CF1325F、CF1364D。

这种图上的神秘构造题直接搞很难，考虑建出一棵 dfs 树。

如果叶子节点（如果根节点度数为 1 也算）数量 c\le\lceil\dfrac n3\rceil，把它们按照 dfs 序排序。\forall i\in[1,\lceil\dfrac c2\rceil]，取 dfs 树上排名为 i 和 i+\lfloor\dfrac c2\rfloor 的点上的路径，数量不超过 \lceil\dfrac n6\rceil，如果不够就随便塞上一些。

证明：对于一个点 u，

• 若没有儿子显然能覆盖。
• 若有一个儿子所有经过它的路径都经过它的儿子，所以可转化为它的儿子 v 的情况。
• 若有两个以上儿子总有一个儿子的叶子节点数量不超过它子树的叶子节点数量的一半，一定能覆盖。

否则 c>\lfloor\dfrac n3\rfloor，dfs 树没有横叉边，所以除了 1 之外的所有叶子节点两两不相连，随便输出其中的 \lfloor\dfrac n3\rfloor 个点即可。