CF81E Pairs

题目描述

给定一颗黑白内向基环树，你要对其进行匹配，让匹配数最多的同时最大化异色匹配。并且给出一种方案。

$1 \le n \le 10^5$。

思路

暴力

考虑流。对于一颗普通的树，进行黑白染色变成二分图，跑网络流即可得到最大匹配。如果是异色匹配费用流即可。对于这道题，不妨直接断开环上的任意一条边 $u \to v$，钦定这条边必须选择或者不选流两次即可。时间复杂度 $\mathcal{O}(n\sqrt n)$。理论可过，而且有人过了，但是卡常。

正解

考虑 dp。对于环上的一条路径 $u \to v \to w$。最多产生一个匹配。所以我们可以先断开 $u \to v$ dp 一次，再断开 $v \to w$ dp 一次。两次 dp 答案取 max 即可。这个 dp 是朴素的，设 $f_{u,0/1}$ 表示 $u$ 子树内，$u$ 是（$1$）否（$0$）可以进行匹配的答案。平凡的转移：

$$f_{u,0} = \sum_{v \in \operatorname{son}(u)}f_{v,1}\\ f_{u,1} = \max\{f_{u,0},\max_{v \in \operatorname{son}(u)}\{(\sum_{k \in\operatorname{son}(v),k \neq v}f_{k,1}) + f_{v,0}+\texttt{是否异色}\}\}$$

然后记一下转移去找匹配就行了。时间复杂度 $\mathcal{O}(n)$。