Mex Tree

3000ms

262144K

Description:

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.

Input:

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

Output:

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

Sample Input:

Sample Output:

Note:

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.

Informação

Provedor Codeforces

Código CF1830D