CF2245E.Tom and Jerry

You are given an undirected tree consisting of $n$ vertices. A simple path $p$ of length $k$ is defined as a sequence of distinct vertices $p_0,p_1,\ldots,p_k$ such that there exists an undirected edge between vertices $p_i$ and $p_{i+1}$ for every $0 \le i \lt k$. A simple path is uniquely identified by the unordered pair of its endpoints, $(p_0,p_k)$. That is, $(u,v)$ and $(v,u)$ represent the same simple path.

Tom and Jerry are playing a game on this tree. The players take turns, with Tom going first. In the $i$-th turn ($i \ge 1$), the current player chooses a simple path $(x_i,y_i)$ that satisfies the following conditions:

• $x_i \ne y_i$.
• The path does not share any edges with any of the previously chosen paths.
• Either $x_i$ or $y_i$ belongs to the path chosen in the $(i-1)$-th turn. Note that this condition only applies when $i \ge 2$.

The player who is unable to choose a valid path on their turn loses the game.

Assuming both Tom and Jerry play optimally, your task is to compute the total number of distinct simple paths Tom can choose in the first turn such that he can guarantee a win.

给你一棵包含 $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）正在这棵树上进行一场游戏。两人轮流行动，汤姆先手。在第 $i$ 轮（$i \ge 1$）中，当前玩家需选择一条满足以下条件的简单路径 $(x_i,y_i)$：

• $x_i \ne y_i$；
• 该路径与之前所有已被选择的路径不共享任何边；
• $x_i$ 或 $y_i$ 至少有一个属于第 $(i-1)$ 轮所选路径上的顶点（注意：此条件仅当 $i \ge 2$ 时适用）。

无法在自己的回合中选出合法路径的玩家判负。

假设汤姆与杰瑞均以最优策略进行游戏，请你计算：汤姆在第一轮中可选择的、能保证其必胜的不同简单路径的总数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$), representing the number of vertices in the tree.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$), representing an undirected edge between vertices $u$ and $v$. It is guaranteed that the edges form a valid tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示树中顶点的数量。

接下来的 $n-1$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u,v \le n$，$u \ne v$），表示顶点 $u$ 与 $v$ 之间的一条无向边。保证这些边构成一棵合法的树。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output an integer representing the total number of distinct simple paths Tom can choose in the first turn such that he can guarantee a win.

对于每个测试用例，输出一个整数，表示 Tom 在第一回合中可以选择的、能保证获胜的不同简单路径的总数。

In the first test case, the tree consists of only two vertices and a single edge between vertex $1$ and vertex $2$. Tom can choose the simple path $(1,2)$ on his first turn. Since this path consumes the only edge in the tree, Jerry will have no unused edges available to form a valid path on his turn. Thus, Jerry is unable to make a move, and Tom wins the game. There is exactly $1$ winning path for Tom.

In the third test case, the tree is a star graph with vertex $2$ at the center, connected to vertices $1, 3, 4,$ and $5$. There are $10$ possible simple paths in total.

One of the winning paths is $(1,3)$:

• On his first turn, Tom chooses $(1,3)$. This path uses edges $(1,2)$ and $(2,3)$, and its vertices are ${1, 2, 3}$. The unused edges remaining in the tree are $(2,4)$ and $(2,5)$.
• On Jerry's turn, he must pick an edge-disjoint path with at least one endpoint in Tom's path ${1, 2, 3}$. The only valid paths Jerry can choose are $(2,4)$ or $(2,5)$. Jerry cannot choose the path $(4,5)$ because its endpoints $4$ and $5$ do not belong to Tom's path ${1, 2, 3}$.
• Suppose Jerry chooses $(2,4)$. His path vertices are now ${2, 4}$.
• On Tom's next turn, he must pick a path with an endpoint in ${2, 4}$. He can simply choose the last remaining path $(2,5)$.
• After this, all edges are exhausted, Jerry has no moves left, and Tom wins.

One of the losing paths is $(1,2)$:

• Suppose Tom starts by choosing $(1,2)$. The vertices on his path are ${1, 2}$, and the remaining edges are $(2,3), (2,4),$ and $(2,5)$.
• Jerry can respond by choosing the path $(2,3)$. This is valid because the endpoint $2$ is on Tom's previous path. The vertices of Jerry's path are ${2, 3}$.
• Tom is now forced to choose an unused path with an endpoint in ${2, 3}$. He must choose either $(2,4)$ or $(2,5)$. Let's say he chooses $(2,4)$.
• Jerry will then easily choose the final remaining path $(2,5)$, as its endpoint $2$ belongs to Tom's previous path ${2, 4}$.
• All edges are now used. Tom cannot make a move on his turn and loses the game.

在第一个测试用例中，树仅包含两个顶点以及连接顶点 $1$ 与顶点 $2$ 的唯一一条边。Tom 在他的第一回合可选择简单路径 $(1,2)$。由于该路径消耗了树中唯一的边，Jerry 在他的回合将没有未使用的边来构成一条合法路径。因此，Jerry 无法进行任何操作，Tom 获胜。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 当前路径顶点集 $\{1, 2, 3\}$ 的路径。Jerry 唯一可选的有效路径是 $(2,4)$ 或 $(2,5)$。他不能选择路径 $(4,5)$，因为其两个端点 $4$ 和 $5$ 均不属于 Tom 的路径顶点集 $\{1, 2, 3\}$。
• 假设 Jerry 选择了 $(2,4)$，则他当前路径的顶点集合为 $\{2, 4\}$。
• 在 Tom 的下一轮中，他必须选择一条至少有一个端点属于 $\{2, 4\}$ 的未使用路径。他只需选择最后一条剩余路径 $(2,5)$ 即可。
• 此后所有边均已被使用，Jerry 无路可走，Tom 获胜。

其中一条失败路径是 $(1,2)$：

• 假设 Tom 首先选择路径 $(1,2)$。该路径的顶点集合为 $\{1, 2\}$，剩余未使用的边为 $(2,3), (2,4), (2,5)$。
• Jerry 可以回应以路径 $(2,3)$。这是合法的，因为其端点 $2$ 属于 Tom 上一轮路径的顶点集 $\{1, 2\}$。Jerry 当前路径的顶点集合为 $\{2, 3\}$。
• Tom 此时被迫选择一条未使用的路径，且该路径至少有一个端点属于 $\{2, 3\}$。他只能在 $(2,4)$ 与 $(2,5)$ 中任选其一。假设他选择了 $(2,4)$。
• 接着 Jerry 可轻松选择最后一条剩余路径 $(2,5)$，因为其端点 $2$ 属于 Tom 上一轮路径的顶点集 $\{2, 4\}$。
• 此时所有边均已使用完毕。Tom 在他的回合无法再进行任何操作，因而输掉游戏。