D. Mex 树

时间限制：每个测试 $3$ 秒
内存限制：每个测试 $256$ MB

给定一棵有 $n$ 个节点的树。对于每个节点，你可以将其染成 $0$ 或 $1$。

一条路径 $(u,v)$ 的值等于从 $u$ 到 $v$ 的最短路径上节点颜色的 MEX$^\dagger$。

一种染色方案的价值等于所有满足 $1 \le u \le v \le 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$ 不在。

输入
每个测试包含多个测试用例。第一行输入一个整数 $t$ $(1 \le t \le 10^4)$，表示测试用例的数量。接下来是各个测试用例的描述。

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

接下来的 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $(1 \le a_i, b_i \le n, a_i \neq b_i)$，表示顶点 $a_i$ 和 $b_i$ 之间的一条边。保证给定的边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，输出任意一种染色方案所能达到的最大价值。

示例输入

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$。之后，考虑所有路径：

• $(1,1)$ 的值为 $1$
• $(1,2)$ 的值为 $2$
• $(1,3)$ 的值为 $2$
• $(2,2)$ 的值为 $0$
• $(2,3)$ 的值为 $2$
• $(3,3)$ 的值为 $1$

这些值的总和为 $8$，这是可能的最大值。