P14309 【MX-S8-T2】配对 题解

Zi_Gao · 2025-10-27 07:23:44 · 题解

出题人题解，欢迎观看视频题解，打不开的把链接https://www.bilibili.com/video/BV1hhsfzYEdc/复制下来打开。

先把树变成有根树之后，考虑从下往上考虑，容易发现对于一个节点 u，其子树最多剩余一个点会继续向上匹配，因为如果有多点没匹配，都会在 u 尽量匹配。

那么 u 到其父亲 p 的边 w，贡献就是：w\left(\sum_{v\in \text{tree(u)}} c_v \bmod 2\right)，为了方便记 f_u=\sum_{v\in \text{tree(u)}}c_v \bmod 2。

提示 1：假设 \sum c_u \equiv 0 \pmod 2 怎么做。

交换 c_u=c_v=0,c_u=c_v=1 都没用，那么这里钦定 c_u=1,c_v=0，相当于是把一个 1 移动到一个 0 上去了。

影响的 f 实际上就是 u 到 v 路径上的 f，并且全部取反，可以使用寻找树最长链等方法计算。

提示 2： 假设 \sum c_u \equiv 1 \pmod 2 怎么做。

把未知的问题转化为已知的问题，这里就是要删去一个点，其实就相当于把这个点移动到了根的父亲上去（假设有这么一个点），也就是让 f 从 u 到根路径上全部取反。

发现 u 子树对上面的影响只有几种不同类型：

1. 交换操作的影响：

   1. 子树内没有要移动走的点，也没有移动了点。
   2. 子树内有一个 0 要移动走。
   3. 子树内有一个 1 要移动走。
   4. 子树内已经有了一个 1 移动到了 0 了。

2. 删去点的影响：

   1. 子树内没删去点。

   2. 子树内删掉了一个 1。

于是设计 dp_{u,a,b} 表示 u 子树交换操作的类型是 a，删除操作的类型是 b，一共 8 个状态。