Rikka with Match

WZH2026-10-092026-10-09

某人号 Sam 尝曰：最大独立集乃树上背包也。

余曰：误人子弟。最大独立集乃贪心也。

给定 $n$ 个点的树，求有多少中割边的方案使得最大匹配大小被 $m$ 整除。

$n\le 5\times10^4,m\le 200$ 。

将最大匹配转化为最大独立集后，首先我们应该想如何刻画最大独立集：

贪心：

按深度从大到小选择点。只要这个点可以选择就选择。

那么我们就可以得出一个 DP 状态并利用上述贪心转移：定义 $f_{i,j,k}$ 为 $i$ 的子树，最大独立集模 $m$ 为 $j$ ，且 $i$ 选择/不选择的方案数。

然后初始化是比较简单的，因为按照贪心，一开始是时候只有 $i$ 一个点，于是必须选择，那么就有 $f_{x,1,1}=1$ ，其余为 $0$ 。

考虑仿照树形背包，逐步加入儿子 $u$ 。

那么对于儿子 $u$ ，我既可以断掉这条边，也可以不断。

Case #1：断

这个时候 $u$ 的选择就与 $x$ 无关了，那么只需要对第二维进行树形背包即可（注意，我写的所有转移的第二维都是在模意义下的）：

f_{x,i,0/1}\leftarrow\sum_{j+k=i}f_{x,j,0/1}(f_{u,k,0}+f_{u,k,1})

此时 $u$ 的选择就会影响 $x$ 了。

那么不妨枚举 $x$ 的状态 $p$ 和 $u$ 的状态 $q$ 。

若 $p=0$ ，则 $x$ 必然不会被选择，那么此时 $u$ 的状态 $q$ 就不会有影响了，因此有转移：

f_{x,i,0}\leftarrow\sum_{j+k=i}f_{x,j,0}(f_{u,k,0}+f_{u,k,1})

若 $p=1,q=0$ ，则根据贪心，此时 $x$ 依然继续选择，因此：

f_{x,i,1}\leftarrow\sum_{j+k=i}f_{x,j,1}f_{u,k,0}

若 $p=1,q=1$ ，那么此时根据贪心， $x$ 的状态要有选择变为不选择，即，最大独立集的大小会 $-1$ 。

那么同样的，我们也可以得出转移：

f_{x,i-1,0}\leftarrow\sum_{j+k=i}f_{x,j,1}f_{u,k,1}

上面的四种转移转移完成后，这题就可以以 $\mathcal{O}(nm^2)$ 的复杂度完成，预期得分 $50$ 。

然后就是一个可能会被遗忘的优化：这个转移本质上只是树形背包的变体，因此只需要在转移的时候，将上界 $m$ 换成 $\min\{m,sz_x\}$ 和 $\min\{m,sz_u\}$ 就行了。

这样就可以做到 $\mathcal{O}(nm)$ 了。