给定一棵 $n$ 个顶点的无根树，保证每个点的度数不超过 $10$。
现在给定树上的 $m$ 条路径，每条路径形如 $u_i \leadsto v_i$，你需要选择其中尽可能多的路径，使得这些路径两两之间没有公共边 (但可以有公共点)。
本题包含多组数据。第一行包含一个正整数 $T$ ($T \leq 100$)，表示数据组数。
对于每组数据，第一行包含一个正整数 $n$ ($2 \leq n \leq 1000$)，表示顶点的个数。
接下来 $n - 1$ 行，每行两个正整数 $a, b$ ($1 \leq a < b \leq n; a \neq b$)，描述树上的一条边。保证这 $n - 1$ 条边恰好构成一棵树。
第 $n + 1$ 行包含一个非负整数 $m$ ($0 \leq m \leq \dbinom n2$)，表示路径的条数。
最后 $m$ 行，每行两个正整数 $u_i, v_i$ ($1 \leq u_i, v_i \leq n; u_i \neq v_i$)，表示一条端点为 $u_i$ 和 $v_i$ 的路径。保证这 $m$ 条路径两两不同。
保证至多有 $20$ 组数据满足 $n > 50$。
对于每组数据，输出一行一个整数，表示能选择的路径数的最大可能值。
考虑使用树形 DP，用 $f_i$ 表示只考虑以 $i$ 为根的子树 (与两端点都在这棵子树中的路径)，能选择的路径数量的最大值 (答案)，于是答案就就是 $f_1$ ($1$ 为根)。
对于转移，首先一个显然的不等式是 $$ f_i \geq \sum_{c \in child \left( i \right)} f_c $$
但是，这只是一个不等关系。还有一些路径是没被考虑的 (可能还会被选上的)，我们称其为 "额外链"。这些 "额外链" 有一个共同特性：经过点 $i$。于是 "额外链" 可以被分为两类：
设 $child \left( i \right) = \left\{ c_1, c_2, \cdots, c_\lambda \right\}$。则考虑边 $\left( c_j, i \right)$，由于这条边至多被一条链所覆盖，因此可以得到每个子树 $subtree \left( c_j \right)$ 中至多有一个点作为 "额外链" 的端点。
由这个性质，可以得到一个推论：存在 $subtree \left( i \right)$ 的最优解，满足对于每个 $1 \leq j \leq \lambda$，在子树 $subtree \left( c_j \right)$ 中也是最优解 (即子树 $subtree \left( c_j \right)$ 中的路径数量等于 $f_{c_j}$)。
反之，设子树 $subtree \left( c_j \right)$ 中不是最优解，因此这一部分的路径数量 $\leq f_{c_j} - 1$。
又因为 $subtree \left( c_j \right)$ 中至多包含 "额外链" 中的一个端点，因此如果有端点在 $subtree \left( c_j \right)$ 中的 "额外链"，我们将其去掉，于是至多减少一条 "额外链"。
而经操作后，$subtree \left( c_j \right)$ 就被 "独立" 开来了 (或者说没有链覆盖边 $\left( c_j, i \right)$)，因此我们将 $subtree \left( c_j \right)$ 中的方案更改为最优方案，从而 (子树中) 路径数量变为 $f_{c_j}$，至少增加 $1$。
从而总路径条数单调不减，而在子树 $subtree \left( c_j \right)$ 中也是最优解。
由于该调整使得满足在子树中也为最优解的子树个数严格增大，故必在有限步内结束。
因此我们可以规定每棵子树都必须达到最优解。那么现在考虑一条第二类 "额外链" $\left( u, v \right)$，其中 $u \in subtree \left( c_\mu \right), v \in subtree \left( c_\nu \right)$。
于是如果这条链可以被选中，那么一个必要条件是，存在 $subtree \left( c_\mu \right)$ 的一组最优解不覆盖链 $c_\mu \leadsto u$。
从而可以想到，我们记录 $F_i$ 表示 $subtree \left( i \right)$ 中满足如下性质的点 $x$ 的集合：存在一组 $subtree \left( c_i \right)$ 的最优解 ($f_i$ 条路径) 不覆盖链 $i \leadsto x$。
因此上面这条 "额外链" 的必要条件就转化为了 $\color {teal} {u \in F_{c_\mu}, v \in F_{c_\nu}}$。
(对第一类 "额外链" $\left( u, i \right)$，必要条件就相当于 $u \in F_{c_\mu}$)
因此，下面不妨假设所有的 "额外链" 都满足上述必要条件。
下面证明，存在最优解，满足对于每个 $1 \leq j \leq \lambda$，若存在端点在 $subtree \left( c_j \right)$ 中的第一类 "额外链"，则它一定在最优解中。
反之设 $subtree \left( c_j \right)$ 中的第一类 "额外链" 没有被选入。
由 $F_{c_j}$ 的定义知，该额外链不可能和子树 $subtree \left( c_j \right)$ 内部冲突。
因此它只能和一条第二类 "额外链" 冲突，我们将这条第二类 "额外链" 换成第一类 "额外链"，路径总数单调不减。
设满足上述条件的 $j$ 有 $C_1$ 个，则我们现在已经得到了一个大小为 $\displaystyle \sum_{c \in child \left( i \right)} f_c + C_1$ 的解，并且所有的解都可以基于这个解考虑。
现在，设 $c_1, c_2, \cdots, c_\lambda$ 是满足没有第一类 "额外链" 能覆盖边 $\left( c_j, i \right)$ 的，故只能考虑用第二类 "额外链" 来覆盖它们。
而每个第二类 "额外链" 需要占据两个 $c_j$，从而这部分模型可以转化成：
有若干个 $\left\{ 1, 2, \cdots, \lambda \right\}$ 上的二元组 $\left( u_i, v_i \right)$，你需要选择尽可能多的二元组使得这些二元组两两没有公共元素。
不难发现，如果将 $\left\{ 1, 2, \cdots, \lambda \right\}$ 看成点，$\left( u_i, v_i \right)$ 看成边，上述问题就是一个一般图最大匹配问题。
(ps: 事实上，原图是不易于一般图最大匹配的：只需构造星图 $S_n$，然后所有路径连接一对叶节点，这样可以将任意一个一般图最大匹配转化为此问题，因此该问题的难度不小于一般图最大匹配)
但是，注意到题目中的粉色条件 (每个点的度数不超过 $10$)，因此可知 $\lambda \leq 10$，于是我们只需要实现一个 $10$ 个点的一般图最大匹配，直接使用状态压缩 DP 即可。
设最终的匹配大小为 $C_2$，则 $$ f_i = \sum_{c \in child \left( i \right)} f_c + C_1 + C_2 $$
当然，别忘了我们还需要维护出集合 $F_i$。
由于第一类 "额外链" 一定出现在最优解中，因此如果存在端点在 $subtree \left( c_j \right)$ 中的 "额外链"，则 $subtree \left( c_j \right) \cap F_i = \varnothing$。
否则，考虑第二类 "额外链"，就相当于将边 $\left( c_j, i \right)$ 去掉 (相当于在辅助图把点 $j$ 去掉) 后仍要有大小为 $C_2$ 的匹配，如果 $j$ 满足这一性质，则 $F_{c_j} \subseteq F_i$，否则 $\left( c_j, i \right)$ 一定会被覆盖，即 $subtree \left( c_j \right) \cap F_i = \varnothing$。
因此最终 $F_i$ 就等于 $\left\{ i \right\}$ 并上所有满足上述条件的 $j$ 的 $F_j$ 的并，使用状态压缩 DP 不难维护出哪些 $j$ 满足条件。
分析一下时间复杂度，状态压缩 DP 的复杂度为 $O \left( \sum\limits_i d \left( i \right) 2^{d \left( i \right)} \right) = O \left( n \cdot 2^\Delta \right)$，建图及维护 $F_i$ 可以使用 bitset，时间复杂度 $O \left( \dfrac {n^2} \omega \right)$，故时间复杂度为 $O \left( n + m + \dfrac {n^2} \omega + n \cdot 2^\Delta \right)$，其中 $\Delta \leq 10$ 为最大度。
#include <bits/stdc++.h>
#define ctz __builtin_ctz
using std::cin;
using std::cout;
const int N = 1023, M = N * 2;
typedef std::bitset <N> bitset;
int n, q, E;
int to[M], first[N], next[M];
int f[N];
bitset F[N], G[N];
inline void up(int &x, const int y) {x < y ? x = y : 0;}
namespace matching {
int n, ALL;
int G[15], f[1054], replaceable;
inline void reset(int n_) {n = n_, memset(G, 0, n << 2);}
inline void link(int x, int y) {G[x] |= 1 << y, G[y] |= 1 << x;}
int main() {
int i, v, S; ALL = ~(-1 << n);
for (i = 1; i <= ALL; ++i)
for (f[i] = f[i & (i - 1)], v = ctz(i), S = G[v] & i; S; S &= S - 1)
up(f[i], f[i & (i - 1) & ~(S & -S)] + 1);
for (replaceable = i = 0; i < n; ++i) replaceable |= (f[ALL & ~(1 << i)] == f[ALL]) << i;
return f[ALL];
}
}
inline void addedge(int u, int v) {
to[++E] = v, next[E] = first[u], first[u] = E;
to[++E] = u, next[E] = first[v], first[v] = E;
}
void dfs(int x, int px = 0) {
int i, j, y, u, v, w, c[15], d = 0, c1[15], d1 = 0; bitset t; f[x] = 0;
for (i = first[x]; i; i = next[i]) if ((y = to[i]) != px) dfs(y, x), c[d++] = y, f[x] += f[y];
assert(d < 11);
for (i = 0; i < d; ++i)
if (y = c[i], (G[x] & F[y]).any()) ++f[x];
else c1[d1++] = y;
matching::reset(d1);
for (i = 0; i + 1 < d1; ++i) {
u = c1[i], t.reset();
for (w = F[u]._Find_first(); w != N; w = F[u]._Find_next(w)) t |= G[w];
for (j = i + 1; j < d1; ++j)
if (v = c1[j], (t & F[v]).any()) matching::link(i, j);
}
f[x] += matching::main(), F[x].set(x);
for (w = matching::replaceable; w; w &= w - 1) F[x] |= F[c1[ctz(w)]];
}
void work() {
int i, u, v; E = 0;
cin >> n, memset(first, 0, (n + 1) << 2);
for (i = 1; i < n; ++i) cin >> u >> v, addedge(u, v);
for (i = 1; i <= n; ++i) F[i].reset(), G[i].reset();
cin >> q;
for (i = 0; i < q; ++i) cin >> u >> v, G[u].set(v), G[v].set(u);
dfs(1), cout << f[1] << '\n';
}
int main() {
int T;
std::ios::sync_with_stdio(false), cin.tie(NULL);
for (cin >> T; T; --T) work();
return 0;
}
坑1：在 dfs 回溯时如果使用全局变量需要注意污染问题，最好先递归完下层节点再进行该层节点的合并。
坑2：可以使用 bitset 的 any 操作减少常数，但是注意不要提前 break 了，也不要在建图时统计「存在第一类 "额外边" 的子树」。