【题解】CF1929E - Sasha and the Happy Tree Cutting

题目链接

https://codeforces.com/contest/1929/problem/E

题目大意

给定一颗 $n$ 个结点的树，给定 $k$ 条树上的路径 $a_{i}, b_{i}$ 。现在要对树上的一些边染色，使得 $k$ 条路径中的每一条路径上都至少有一条边被染色，问最少染多少条边。

数据范围

$2 \leq n \leq 10^{5}$
$1 \leq k \leq 20$

解题思路

考虑统计每一条边被那些路径覆盖，假设覆盖第 $i$ 边的路径集合为 $S_{i}$ ，那就是要找到一个长度最短的序列 $p_{1}, p_{2}, \dots, p_{m}$ 使得 $S_{P_{1}} \cup S_{p_{2}} \cup \dots \cup S_{p_{m}} = {1, 2, \dots, k}$ 。

我们联想到了状压 dp，但发现直接 dp 复杂度是 $O (n \cdot 2^{k})$ ，是行不通的。

因为路径条数非常少，我们可以猜测本质不同的集合 $S_{i}$ 的个数跟 $k$ 是一个级别的。

证明可以考虑建出这 $2 k$ 个点的虚树，由于虚树上最多只有 $4 k - 1$ 个结点， $4 k - 2$ 条边，所以最多只有 $4 k - 2$ 种本质不同的 $S_{i}$ 。

有了上面的结论我们就可以直接 $O (n k)$ 地 dp 了。

参考代码

https://codeforces.com/contest/1929/submission/246624331