题意：
给定一棵 \(n\) 个节点数和 \(k\) 条路径 \((a_i, b_i)\)，求至少将多少条边染色，使得给定路径都至少有一条染色的边。
\(n \le 10^5, k \le 20\)。
思路：
好题。
显然状压 \(dp\)，\(dp[S]\) 表示至少染多少条边使得 \(S\) 中的路径都满足条件。正常思路是枚举子集转移，考虑 \(T \sub S\) 能否有一条边同时经过 \(T\) 中所有路径，但是这样是 \(O(3^n)\) 的。
考虑建出这 \(2k\) 个点的虚树，我们定义 \(V_i\) 表示第 \(i\) 条边经过的所有路径，结合虚树的知识，不难发现本质不同的 \(V_i\) 是 \(O(k)\) 的。
于是我们考虑用这些转移，采用刷表法，写成 \(dp[S | v_i] = min(dp[S | v_i], dp[S] + 1)\)，这样时间复杂度就是 \(O(k2^k)\) 的了。
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, k;
vector<int> e[N];
int d[N] = {0};
int p[N] = {0};
void dfs(int x, int pr, int dth) {
p[x] = pr, d[x] = dth;
for (auto i: e[x])
if (i != pr)
dfs(i, x, dth + 1);
}
int val[N] = {0};
void upd(int a, int b, int v) {
if (a == b)
return;
if (d[a] < d[b])
swap(a, b);
val[a] += v;
upd(p[a], b, v);
}
int dp[(1 << 20) + 5] = {0};
void slv() {
cin >> n;
for (int i = 1; i <= n; i++)
val[i] = 0, e[i].clear();
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 1, 1);
cin >> k;
for (int i = 1, a, b; i <= k; i++) {
cin >> a >> b;
upd(a, b, (1 << (i - 1)));
}
sort(val + 1, val + n + 1);
int cur = unique(val + 1, val + n + 1) - val - 1;
for (int S = 0; S < (1 << k); S++)
dp[S] = 2e9;
dp[0] = 0;
for (int S = 0; S < (1 << k); S++)
for (int i = 1; i <= cur; i++)
dp[(S | val[i])] = min(dp[(S | val[i])], dp[S] + 1);
cout << dp[(1 << k) - 1] << endl;
}
int main() {
int T;
cin >> T;
while (T--)
slv();
return 0;
}