CF1929E Sasha and the Happy Tree Cutting

Sasha 因为又一次赢得比赛而获得了一棵有 $n$ 个节点的树 $^{\dagger}$ 作为奖品。然而，在庆祝胜利回家后，他发现这棵树有些部分丢失了。Sasha 记得他曾经给这棵树的一些边涂过色。他可以确定，对于 $k$ 对顶点 $(a_1, b_1), \ldots, (a_k, b_k)$ 中的每一对，他都至少在连接 $a_i$ 和 $b_i$ 的简单路径 $^{\ddagger}$ 上涂过一条边。 Sasha 不记得他究竟涂了多少条边，所以他请你帮忙计算，为了满足上述条件，他最少可能涂了多少条边。 $^{\dagger}$ 一棵树是一个无环连通无向图。 $^{\ddagger}$ 简单路径指的是每个顶点最多经过一次的路径。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 10^5$）——表示树的节点数。 接下来的 $n-1$ 行描述树的边。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，$u_i \ne v_i$），表示第 $i$ 条边连接了 $u_i$ 和 $v_i$ 两个节点。 接下来一行包含一个整数 $k$（$1 \leq k \leq 20$）——表示需要满足的顶点对数量。 接下来的 $k$ 行描述这些顶点对。第 $j$ 行包含两个整数 $a_j$ 和 $b_j$（$1 \leq a_j, b_j \leq n, a_j \neq b_j$），表示第 $j$ 对顶点。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。保证所有测试用例中 $2^k$ 的总和不超过 $2^{20}$。

对于每个测试用例，输出一个整数，表示 Sasha 至少需要涂色的边数。

在第一个测试用例中，Sasha 只需涂色一条边 $(1, 2)$。这样，$1$ 和 $3$ 之间的简单路径、$4$ 和 $1$ 之间的简单路径上都至少有一条被涂色的边。  在第二个测试用例中，Sasha 可以涂色边 $(1, 6)$ 和 $(1, 3)$。  由 ChatGPT 4.1 翻译