Resourceful Caterpillar Sequence
Contest: Good Bye 2024: 2025 is NEAR
Difficulty rating: 1900
Tags: dfs and similar, dp, games, graphs, greedy, trees

There is a tree consisting of $$$n$$$ vertices. Let a caterpillar be denoted by an integer pair $$$(p, q)$$$ ($$$1 \leq p, q \leq n$$$, $$$p \neq q$$$): its head is at vertex $$$p$$$, its tail is at vertex $$$q$$$, and it dominates all the vertices on the simple path from $$$p$$$ to $$$q$$$ (including $$$p$$$ and $$$q$$$). The caterpillar sequence of $$$(p, q)$$$ is defined as the sequence consisting only of the vertices on the simple path, sorted in the ascending order of the distance to $$$p$$$.

Nora and Aron are taking turns moving the caterpillar, with Nora going first. Both players will be using his or her own optimal strategy:

- They will play to make himself or herself win;
- However, if it is impossible, they will play to prevent the other person from winning (thus, the game will end in a tie).

In Nora's turn, she must choose a vertex $$$u$$$ adjacent to vertex $$$p$$$, which is not dominated by the caterpillar, and move all the vertices in it by one edge towards vertex $$$u$$$$$$^{\text{∗}}$$$. In Aron's turn, he must choose a vertex $$$v$$$ adjacent to vertex $$$q$$$, which is not dominated by the caterpillar, and move all the vertices in it by one edge towards vertex $$$v$$$. Note that the moves allowed to the two players are different.

Whenever $$$p$$$ is a leaf$$$^{\text{†}}$$$, Nora wins$$$^{\text{‡}}$$$. Whenever $$$q$$$ is a leaf, Aron wins. If either initially both $$$p$$$ and $$$q$$$ are leaves, or after $$$10^{100}$$$ turns the game has not ended, the result is a tie.

Please count the number of integer pairs $$$(p, q)$$$ with $$$1 \leq p, q \leq n$$$ and $$$p \neq q$$$ such that, if the caterpillar is initially $$$(p, q)$$$, Aron wins the game.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) — the number of vertices in the tree.

The following $$$n - 1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

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

Output format:
For each test case, output a single line containing an integer: the number of integer pairs $$$(p, q)$$$ which make Aron win.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, all possible caterpillars are $$$(1, 2)$$$ and $$$(2, 1)$$$, resulting in a tie at the beginning, since both $$$p$$$ and $$$q$$$ are leaves.

In the second test case, the caterpillars that allow Aron to win are the following: $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$. Let's look at some specific caterpillars.

- For the caterpillar $$$(1, 5)$$$: vertex $$$p = 1$$$ is not a leaf, but vertex $$$q = 5$$$ is, so Aron wins at the beginning.
- For the caterpillar $$$(2, 1)$$$: vertex $$$p = 2$$$ is not a leaf, neither is vertex $$$q = 1$$$. In Nora's first move, she can choose to move the caterpillar towards vertex $$$5$$$, therefore the caterpillar becomes $$$(5, 2)$$$, and vertex $$$p = 5$$$ is a leaf, so Nora will win.

Example input:
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

Example output:
0
6
40
27
171

Editorial: