题目链接
https://codeforces.com/contest/1929/problem/E
题目大意
给定一颗 \(n\) 个结点的树，给定 \(k\) 条树上的路径 \(a_i, b_i\)。现在要对树上的一些边染色，使得 \(k\) 条路径中的每一条路径上都至少有一条边被染色，问最少染多少条边。
数据范围
- \(2\le n \le 10^{5}\)
- \(1 \le k \le 20\)
解题思路
考虑统计每一条边被那些路径覆盖，假设覆盖第 \(i\) 边的路径集合为 \(S_i\)，那就是要找到一个长度最短的序列 \(p_1, p_2, \cdots, p_m\) 使得 \(S_{P_1} \cup S_{p_2} \cup \cdots \cup S_{p_m} = \{1, 2, \cdots, k\}\)。
我们联想到了状压 dp，但发现直接 dp 复杂度是 \(O(n\cdot 2^{k})\)，是行不通的。
因为路径条数非常少，我们可以猜测本质不同的集合 \(S_i\) 的个数跟 \(k\) 是一个级别的。
证明可以考虑建出这 \(2k\) 个点的虚树，由于虚树上最多只有 \(4k - 1\) 个结点，\(4k - 2\) 条边，所以最多只有 \(4k - 2\) 种本质不同的 \(S_i\)。
有了上面的结论我们就可以直接 \(O(nk)\) 地 dp 了。