← 返回题目列表

Codeforces · 2053/E

E. 足智多谋的毛毛虫序列

中文机器翻译题面 查看原题

有一棵由 $$$n$$$ 个顶点组成的树。设一条毛毛虫用整数对 $$$(p, q)$$$ ($$$1 \leq p, q \leq n$$$, $$$p \neq q$$$) 表示:它的头位于顶点 $$$p$$$,尾部位于顶点 $$$q$$$,并且它支配从 $$$p$$$ 到 $$$q$$$ 的简单路径上的所有顶点(包括$$$p$$$ 和 $$$q$$$)。 $$$(p, q)$$$ 的毛毛虫序列定义为仅由简单路径上的顶点组成的序列,按照到 $$$p$$$ 的距离升序排序。

诺拉和阿伦轮流移动毛毛虫,诺拉先移动。两个玩家都将使用他或她自己的最佳策略:

- 他们会为了让自己获胜而比赛;
- 但是,如果不可能,他们会阻止对方获胜(因此,游戏将以平局结束)。

轮到诺拉,她必须选择一个与顶点 $$$p$$$ 相邻且不受毛虫支配的顶点 $$$u$$$,并将其中所有顶点向顶点 $$$u$$$$$$^{\text{*}}$$$ 移动一条边。轮到阿伦,他必须选择一个与顶点 $$$q$$$ 相邻且不受毛虫支配的顶点 $$$v$$$,并将其中的所有顶点向顶点 $$$v$$$ 移动一条边。请注意,两名玩家允许的动作是不同的。

每当 $$$p$$$ 是叶子$$$^{\text{†}}$$$时,Nora 获胜$$$^{\text{‡}}$$$。每当 $$$q$$$ 是一片叶子时,Aron 就获胜。如果最初 $$$p$$$ 和 $$$q$$$ 都离开,或者在 $$$10^{100}$$$ 回合后游戏尚未结束,则结果为平局。

请计算整数对 $$$(p, q)$$$ 的数量,其中 $$$1 \leq p, q \leq n$$$ 和 $$$p \neq q$$$,这样,如果毛毛虫最初是 $$$(p, q)$$$,则 Aron 赢得游戏。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2\cdot 10^4$$$) - 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) - 树中的顶点数。

以下 $$$n - 1$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$),表示顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证给定的边形成一棵树。

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

输出

对于每个测试用例,输出一行包含一个整数:使 Aron 获胜的整数对 $$$(p, q)$$$ 的数量。

示例

输入 #1

5
2
1 2
5
1 2
1 3
2 4
2 5
12
1 6
11 2
4 8
12 3
2 7
6 12
8 1
2 3
5 12
9 2
10 3
10
1 2
2 3
3 4
4 5
5 6
4 7
6 8
4 9
4 10
25
1 16
11 22
6 14
3 1
20 14
23 17
25 19
10 11
3 18
10 6
2 21
4 5
11 12
4 9
9 13
8 6
6 1
3 7
8 19
10 24
15 13
1 2
3 4
17 8

输出 #1

0
6
40
27
171

注意

在第一个测试用例中,所有可能的毛毛虫都是 $$$(1, 2)$$$ 和 $$$(2, 1)$$$,导致开头平局,因为 $$$p$$$ 和 $$$q$$$ 都是叶子。

在第二个测试用例中,允许 Aron 获胜的毛毛虫如下:$$$(1, 3)$$$、$$$(1, 4)$$$、$$$(1, 5)$$$、$$$(2, 3)$$$、$$$(2, 4)$$$、$$$(2, 5)$$$。让我们看看一些具体的毛毛虫。

- 对于毛毛虫 $$$(1, 5)$$$:顶点 $$$p = 1$$$ 不是叶子,但顶点 $$$q = 5$$$ 是叶子,所以 Aron 一开始就赢了。
- 对于毛毛虫 $$$(2, 1)$$$:顶点 $$$p = 2$$$ 不是叶子,顶点 $$$q = 1$$$ 也不是叶子。在诺拉的第一步中,她可以选择将毛毛虫移向顶点$$$5$$$,因此毛毛虫变成$$$(5, 2)$$$,而顶点$$$p = 5$$$是一片叶子,所以诺拉获胜。