自动搬运

查看原文

来自洛谷，原作者为

	dspt その日まで 飛ばあげ 嵐がさわってゆくまで

搬运于2025-08-24 22:59:38，当前版本为作者最后更新于2024-06-17 11:46:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

一道考查二分图最大匹配的好题，遗憾没有场切。

题目分为两个部分，分别是构造 DFS 序和构造操作方案。

构造 DFS 序

根据 DFS 序的性质，我们知道一棵子树的 DFS 序是连续的。如果我们钦定了点 $p$ 在 DFS 序中为第 $i$ 个点，那么子树 $p$ 对应的 DFS 序即为 $[i,i+s_p-1]$（ $s_p$ 表示子树 $p$ 的大小），可以预处理得到。

这启示我们设计一个 DP，$f_{p,i}=0/1$ 表示子树 $p$ 能否与 DFS 序 $[i,i+s_p-1]$ 匹配，答案就是 $f_{1,1}$。这是一个树形 DP 的形式，考虑如何由孩子的信息合并到根。本题有一个很关键的性质：其满足对于任意两个深度相同的结点，它们的儿子数也相同（也就是说深度相同的点子树大小相同）。我们再想想 $f_{p,i}=1$ 意味着什么。对 $p$ 而言，该点的点权可以为 $w_p,w_p+f_p,w_p+c_{a_{f_p}}$（ $a_{f_p}$ 表示 $f_p$ 在 DFS 序中的位置），这三者中只要有一个等于 $c_i$ 即可；对 $u$ 而言（令 $u$ 是 $p$ 的某个孩子），$u$ 需要确定一个排名 $j$（即它在 $p$ 的儿子中第 $j$ 个被遍历到）满足 $f_{u,i+1+(j-1)s_u}=1$。也就是说我们要找一组孩子和排名一一对应的关系。容易想到二分图匹配。设 $p$ 有 $k$ 个孩子，对于孩子 $u$，计算 $f_{u,i+1+(j-1)s_u}(1\leqslant j\leqslant k)$，如果 $f_{u,i+1+(j-1)s_u}=1$，则在二分图上在左部点 $u$ 和右部点 $j$ 之间连一条边。一一对应的关系就是二分图上的完美匹配！也就是说，我们把 $f_{p,i}=0/1$ 转化成了构造出的二分图是否有完美匹配。因为后面还要构造方案，这里采用匈牙利算法，比较方便。

每次求出 $f_{p,i}$ 后，我们把 DFS 孩子的顺序存在一个 vector 中。我们从根节点开始构造答案，先把 $p$ 放入答案 DFS 序，再按照 vector中的顺序递归求解 $f_{u,i+1+(j-1)s_u}$ 即可。

上述做法时间复杂度分析困难。有两个角度可以优化：把匈牙利算法换成最大流；计算 $f_{p,i}$ 可能重复多次，可以记忆化；但实际上都不需要，可以直接通过。

构造操作方案

上部分说了，每个点的点权可以有 $w_p,w_p+f_p,w_p+c_{a_{f_p}}$ 三种情况。第一种情况显然不用操作，第二种情况应该在 $f_p$ 操作前操作，第三种情况应该在 $f_p$ 操作后操作。

于是我们可以维护一个 deque，先按 DFS 序的顺序判断每个点 $p$ 是否满足第二种情况，如果满足则 push_front。第三种情况则可以用 BFS，把已经满足条件的点放入queue中，每次取出队首 $p$，遍历每个 $p$ 的孩子 $u$，判断其是否满足第三种情况，如果满足则 push_back 并放入队列中。

这部分时间复杂度是 $O(n)$。

后记

#20 数据好强，我跑了 869ms，其余点都短于 100ms。

好像还有一种不用二分图最大匹配的很厉害的做法，但是我不会。

祝大家 NOI 2024 RP++！