Luogu7026 [NWRRC2017]Hidden Supervisors

题意：给定一个 个点的内向森林，其中 号点为某个树的根。

你需要将这个森林连成一棵以 为根的有根树，并使得最终树（对应的无根树）的最大匹配尽可能大。

，时限。

---

最终方案显然是除了 外每个根连出一条边。

---

• 树上最大匹配的贪心 ：从深往浅考虑，每个点若能匹配父亲则匹配。

  注意，若占用根的最大匹配和不占根的最大匹配大小相同，贪心会得出不占根的方案。

我们考虑逐棵树考虑根的连边情况，且要求新的小树 必须连接到 所在的大树 上。

假设我们已经确定了一种树的排列，如何构造最优方案。（显然每种方案都能对应一种排列）

记准备接到大树 上的小树为 。

记 为 的最大匹配。由于只加了一条边，连接后最大匹配的上界显然为 。

观察连接之后贪心的形为。由于贪心从浅到深考虑， 内部的匹配不会变化。

记 的根为 。

• 含

  此时新边的深端（ 的根）已经被占用，故新边一定不会被选中。 原有的匹配均保持。

• 不含

  容易想到，若 中存在非匹配点，则将 与之连接，能多出一个匹配边。这已经达到上界。

  否则，若 中不存在非匹配点，考虑点集 ，它们之中的匹配才可能变化。但现在满匹配仅多加一个点，显然匹配不可能增大。

综上，我们证明了 ：

加入 时，若 的根为非匹配点，且 中存在非匹配点 ，则连接 并使匹配加一。

若条件不满足，匹配不可能增大，为避免影响匹配情况（不便考虑），直接令 与 相连，不难发现此时可以认为贪心算法不会改动匹配。

---

• 观察如上算法的行为：

  记顺序为 ，其中 肯定是 所在的树。

  能提供若干非匹配点（可能包括根）。

  对于 ，若根非匹配，选择一个非匹配点连接。若根已匹配，或找不到非匹配点，则弃疗，直接连向 。不要忘记添加新的非匹配点。

接下来进一步考虑：何种顺序才是最优的？

我们的目标是尽量让更多的树加入时能新增匹配，这和现存的非匹配点有关。不难想到经典的贪心：根已匹配的树无要求，先直接圈接入，接下来在根非匹配的树中，让非匹配点更多的树打头阵。