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.

给你一棵包含 $n$ 个节点的树。对每个节点，你将其染成 $0$ 或 $1$。

路径 $(u,v)$ 的值等于 $u$ 到 $v$ 的最短路径上所有节点颜色所构成数组的 MEX$^\dagger$。

一种染色方案的值定义为所有满足 $1 \leq u \leq v \leq n$ 的路径 $(u,v)$ 的值之和。

该树的所有染色方案中，最大可能的值是多少？

$^{\dagger}$ 数组的 MEX（最小未出现值）是指不属于该数组的最小非负整数。例如：

• $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 不在该数组中。
• $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 在该数组中，但 $2$ 不在。
• $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 都在该数组中，但 $4$ 不在。

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

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示树中节点的数量。

每个测试用例接下来的 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n,\, a_i \neq b_i$），表示节点 $a_i$ 与 $b_i$ 之间存在一条边。保证所给的边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $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.

在第一个样例中，我们将顶点 $2$ 染成颜色 $1$，顶点 $1$ 和 $3$ 染成颜色 $0$。随后，我们考虑所有路径：

• $(1,1)$，其值为 $1$
• $(1,2)$，其值为 $2$
• $(1,3)$，其值为 $2$
• $(2,2)$，其值为 $0$
• $(2,3)$，其值为 $2$
• $(3,3)$，其值为 $1$

我们注意到这些值的总和为 $8$，这是可能的最大值。