P10610 异界之门 题解

· · 题解

前言

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

题目分为两个部分，分别是构造 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++！