# Resourceful Caterpillar Sequence

## Problem Description

Endless Repeating 7 Days

— r-906, [Panopticon](https://www.youtube.com/watch?v=_-Vd0ZGB-lo)



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.

 $ ^{\text{∗}} $ In other words: Let the current caterpillar sequence be $ c_1, c_2, \ldots, c_k $ , then after the move, the new caterpillar sequence becomes $ d(u, c_1), d(u, c_2), \ldots, d(u, c_k) $ . Here, $ d(x, y) $ is the next vertex on the simple path from $ y $ to $ x $ .

 $ ^{\text{†}} $ In a tree, a vertex is called a leaf if and only if its degree is $ 1 $ .

 $ ^{\text{‡}} $ Therefore, Nora never fails to choose a vertex $ u $ when the game has not ended. The same goes for Aron.

## 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.

## Sample #1

### Sample Input #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
```

### Sample Output #1

```
0
6
40
27
171
```

## Hint

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.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: dfs and similar, dp, games, graphs, greedy, trees