CF2053E Resourceful Caterpillar Sequence

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.

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

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

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.