310418: CF1830D. Mex Tree

D. Mex Treetime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

ExampleInput

4
3
1 2
2 3
4
1 2
1 3
1 4
10
1 2
1 3
3 4
3 5
1 6
5 7
2 8
6 9
6 10
1

Output

8
15
96
1

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.

题目大意：Mex树

给定一个有n个节点的树，你可以将每个节点染成0或1。一条路径(u,v)的价值等于u和v之间最短路径上节点颜色的Mex值。一种染色的价值等于所有路径(u,v)的价值之和，其中1≤u≤v≤n。求树的最大可能染色价值。

输入数据格式：
- 第1行：一个整数t(1≤t≤10^4)，表示测试用例的数量。
- 每个测试用例：
- 第1行：一个整数n(1≤n≤2×10^5)，表示树的节点数量。
- 接下来n-1行：每行两个整数a_i和b_i(1≤a_i,b_i≤n, a_i≠b_i)，表示节点a_i和b_i之间有一条边。保证给定的边构成一棵树。

输出数据格式：
- 对于每个测试用例，输出树的最大可能染色价值。

示例：
输入：
```
4
3
1 2
2 3
4
1 2
1 3
1 4
10
1 2
1 3
3 4
3 5
1 6
5 7
2 8
6 9
6 10
1
```
输出：
```
8
15
96
1
```

注意：在第一个示例中，我们将节点2染成1，节点1和3染成0。考虑所有路径的价值，我们注意到价值的总和是8，这是可能的最大值。题目大意：Mex树 给定一个有n个节点的树，你可以将每个节点染成0或1。一条路径(u,v)的价值等于u和v之间最短路径上节点颜色的Mex值。一种染色的价值等于所有路径(u,v)的价值之和，其中1≤u≤v≤n。求树的最大可能染色价值。 输入数据格式： - 第1行：一个整数t(1≤t≤10^4)，表示测试用例的数量。 - 每个测试用例： - 第1行：一个整数n(1≤n≤2×10^5)，表示树的节点数量。 - 接下来n-1行：每行两个整数a_i和b_i(1≤a_i,b_i≤n, a_i≠b_i)，表示节点a_i和b_i之间有一条边。保证给定的边构成一棵树。 输出数据格式： - 对于每个测试用例，输出树的最大可能染色价值。 示例： 输入： ``` 4 3 1 2 2 3 4 1 2 1 3 1 4 10 1 2 1 3 3 4 3 5 1 6 5 7 2 8 6 9 6 10 1 ``` 输出： ``` 8 15 96 1 ``` 注意：在第一个示例中，我们将节点2染成1，节点1和3染成0。考虑所有路径的价值，我们注意到价值的总和是8，这是可能的最大值。