题目描述

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

1n1051 \le n \le 10^5

思路

暴力

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

正解

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

fu,0=vson(u)fv,1fu,1=max{fu,0,maxvson(u){(kson(v),kvfk,1)+fv,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{是否异色}\}\}

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