有一棵由 $$$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$$$是一片叶子,所以诺拉获胜。