CF1830D.Mex Tree

You are given a tree with $n$ nodes. For each node, you either color it in $0$ or $1$ .

The value of a path $(u,v)$ is equal to the MEX $^\dagger$ of the colors of the nodes from the shortest path between $u$ and $v$ .

The value of a coloring is equal to the sum of values of all paths $(u,v)$ such that $1 \leq u \leq v \leq n$ .

What is the maximum possible value of any coloring of the tree?

$^{\dagger}$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of $[2,2,1]$ is $0$ , because $0$ does not belong to the array.
• The MEX of $[3,1,0,1]$ is $2$ , because $0$ and $1$ belong to the array, but $2$ does not.
• The MEX of $[0,3,1,2]$ is $4$ because $0$ , $1$ , $2$ , and $3$ belong to the array, but $4$ does not.

Each test contains multiple test cases. The first line of input contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. The description of test cases follows.

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

The following $n-1$ lines of each test case contains $2$ integers $a_i$ and $b_i$ ( $1 \leq a_i, b_i \leq n, a_i \neq b_i$ ) — indicating an edge between vertices $a_i$ and $b_i$ . It is guaranteed that the given edges form a tree.

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

For each test case, print the maximum possible value of any coloring of the tree.

In the first sample, we will color vertex $2$ in $1$ and vertices $1,3$ in $0$ . After this, we consider all paths:

• $(1,1)$ with value $1$
• $(1,2)$ with value $2$
• $(1,3)$ with value $2$
• $(2,2)$ with value $0$
• $(2,3)$ with value $2$
• $(3,3)$ with value $1$

We notice the sum of values is $8$ which is the maximum possible.