CF2245E Tom and Jerry

给定一棵有 $n$ 个顶点的无向树。一条长度为 $k$ 的简单路径 $p$ 定义为一个由不同顶点 $p_0, p_1, \ldots, p_k$ 组成的序列，且对于每个 $0 \le i < k$，在顶点 $p_i$ 和 $p_{i+1}$ 之间都存在一条无向边。一条简单路径可以由其两个端点的无序对 $(p_0, p_k)$ 唯一标识。也就是说，$(u, v)$ 和 $(v, u)$ 代表同一条简单路径。 Tom 和 Jerry 在这棵树上玩一个游戏。两名玩家轮流行动，Tom 先手。在第 $i$ 次回合（$i \ge 1$），当前玩家需要选择一条满足下列条件的简单路径 $(x_i, y_i)$： - $x_i \ne y_i$。 - 该路径没有与之前已经选择过的任何路径共享边。 - 当 $i \ge 2$ 时，$x_i$ 或 $y_i$ 必须属于上一个回合所选路径中的顶点。注意，这个条件仅在 $i \ge 2$ 时适用。 若某一回合玩家无法选择合法路径，则该玩家输掉游戏。 假设两人都采取最优策略，请你计算 Tom 在第一回合能确保自己获胜的、可以选择的不同简单路径的总数。

输入包含多组测试数据。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。接下来的描述为每个测试用例： 每个测试用例的第一行为一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示树的顶点数。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示 $u$ 和 $v$ 之间有一条无向边。 保证所有输入的边组成一棵合法的树。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示 Tom 首回合能确保获胜的不同简单路径的总数。

在第一个测试用例中，树仅有两个顶点 $1$ 和 $2$，以及它们之间的一条边。Tom 可以在第一回合选择简单路径 $(1,2)$。因为该路径耗尽了树中唯一一条边，Jerry 在他的轮次上将无法选择边，从而无法行动。所以 Tom 获胜，共有 $1$ 条获胜路径。 在第三个测试用例中，树是一个以 $2$ 为中心的星状图，与顶点 $1, 3, 4, 5$ 相连。总共有 $10$ 条简单路径。 其中一条获胜路径是 $(1,3)$： - 首回合，Tom 选择 $(1,3)$，该路径使用了 $(1,2)$ 和 $(2,3)$ 两条边，路径顶点集为 $\{1, 2, 3\}$。树中剩余未使用的边为 $(2,4)$ 和 $(2,5)$。 - Jerry 轮次，他必须选择一条与已选路径无公共边，且至少有一个端点属于 Tom 所选顶点集的路径。唯一合法的选项是 $(2,4)$ 或 $(2,5)$。Jerry 不能选 $(4,5)$，因为 $4$ 和 $5$ 都不属于 Tom 的路径顶点集。 - 假如 Jerry 选择 $(2,4)$，路径顶点集变为 $\{2, 4\}$。 - Tom 接下来可以选择剩下的唯一路径 $(2,5)$。 - 全部边都被用光后，Jerry 无路可选，Tom 获胜。 一条失败的起手路径是 $(1,2)$： - 若 Tom 选 $(1,2)$，路径顶点集为 $\{1, 2\}$，剩余边有 $(2,3), (2,4), (2,5)$。 - Jerry 可以选 $(2,3)$，因为 $2 \in \{1,2\}$。路径顶点集为 $\{2,3\}$。 - Tom 被迫只能在 $\{2,3\}$ 内选 $(2,4)$ 或 $(2,5)$，比如选 $(2,4)$。 - Jerry 再选剩余 $(2,5)$。 - 此时所有边都用完了，Tom 无法行动，他输掉游戏。 由 ChatGPT 5 翻译