[IOI2007] training 训练路径

大意

给定一个无向图, 有树边和非树边, 删去若干条非树边, 使得图中不存在偶环 (点不得出现两次), 求删去最小边权.

题解

限制

考虑每条非树边 $e$, 设 $d(e)$ 为 $e$ 的两端在树上的距离.

1. 当 $d(e)$ 为奇数时, 加上 $e$ 就会形成偶环, 显然不行.

2. 此外, 两条非树边不能重叠, 如下图所示:

   

   图中绿色的边为非树边. 此时, 红色路径就构成了一个环. 证明: 由 1 , $x + y$, $y + z$ 均为偶数, 红色长 $x + z + 2 = (x + y) + (y + z) - 2y + 2$ 显然也是偶数.

   下图同理

   

综上, 合法的图应该是这样的

树形dp + 状压dp

可以用 树形dp 和 状态压缩 解决.

可以把问题转化为合法地加上的最大边权.

设 $f_{u, S}$ 为在 $u$ 的子树中, 不考虑子集合 $S$ 的最大边权.

显然有 $f_{u, S} \ge f_{u, S'}, S' \subseteq S$

转移情况:

1. 从儿子直接转移 $f_{u, S} = \sum_{v \in son(u), v \not\in S} f_{v, \emptyset}$

2. 存在 $u \in x \to y$ 且 $x, y \in sons(u)$, 显然 $u = \operatorname{lca}(x, y)$

   设 $x \to y$ 为 $\{x, p_1, p_2, \cdots , p_n, u, q_m, q_{m - 1}, \cdots, q_1, y\}$.

   设 $a$ 为贡献, 那么: (认为 $x = p_0, y = q_0$)

   $$a = f_{x, \emptyset} + \sum_{i = 1}^{n} f_{p_i, {\{p_{i - 1}\}}} + f_{y, \emptyset} + \sum_{i = 1}^{m} f_{q_i, \{q_{i - 1}\}}$$

   转移为

   $$f_{u, S \cup \{x, y\}} = f_{u, S} + a (x, y \not\in S)$$