题目描述

小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：

• $\red 1$. 一个大小为 $\red{n}$ 的树由 $\red{n}$ 个结点与 $\red{n − 1}$ 条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。
• $\red 2$. 对于一个大小为 $\red{n}$ 的树与任意一个树中结点 $\red{c}$，称 $\red{c}$ 是该树的重心当且仅当在树中删去 $\red{c}$ 及与它关联的边后，分裂出的所有子树的大小均不超过 $\red{\lfloor \frac{n}{2} \rfloor}$（其中 $\red{\lfloor x \rfloor}$ 是下取整函数）。对于包含至少一个结点的树，它的重心只可能有 $\red{1}$ 或 $\red{2}$ 个。

课后老师给出了一个大小为 $\red{n}$ 的树 $\red{S}$，树中结点从 $\red{1 \sim n}$ 编号。小简单的课后作业是求出 $\red{S}$ 单独删去每条边后，分裂出的两个子树的重心编号和之和。即：

$\red{\sum_{(u,v)\in E}\left(\sum_{x\in c(S'_u)} x+\sum_{y\in c(S'_v)} y\right)}$

上式中，$\red{E}$ 表示树 $\red{S}$ 的边集，$\red{(u, v)}$ 表示一条连接 $\red{u}$ 号点和 $\red{v}$ 号点的边。$\red{S'_u}$ 与 $\red{S'_v}$ 分别表示树 $\red{S}$ 删去边 $\red{(u, v)}$ 后，$\red{u}$ 号点与 $\red{v}$ 号点所在的被分裂出的子树，$\red{c(S)}$ 表示树 $\red{S}$ 重心的集合。

小简单觉得作业并不简单，只好向你求助，请你教教他。

输入格式

本题输入包含多组测试数据。

第一行一个整数 $\red{T}$ 表示数据组数。

接下来依次给出每组输入数据，对于每组数据：

第一行一个整数 $\red{n}$ 表示树 $\red{S}$ 的大小。

接下来 $\red{n − 1}$ 行，每行两个以空格分隔的整数 $\red{u_i, v_i}$，表示树中的一条边 $\red{(u_i, v_i)}$。

输出格式

共 $\red{T}$ 行，每行一个整数，第 $\red{i}$ 行的整数表示：第 $\red{i}$ 组数据给出的树单独删去每条边后，分裂出的两个子树的重心编号和之和。

样例

输入样例

2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7

输出样例

32
56

样例说明

对于第一组数据：

删去边 $\red{(1, 2)}$，$\red{1}$ 号点所在子树重心编号为 $\red{\{1\}}$，$\red{2}$ 号点所在子树重心编号为 $\red{\{2, 3\}}$。

删去边 $\red{(2, 3)}$，$\red{2}$ 号点所在子树重心编号为 $\red{\{2\}}$，$\red{3}$ 号点所在子树重心编号为 $\red{\{3, 5\}}$。

删去边 $\red{(2, 4)}$，$\red{2}$ 号点所在子树重心编号为 $\red{\{2, 3\}}$，$\red{4}$ 号点所在子树重心编号为 $\red{\{4\}}$。

删去边 $\red{(3, 5)}$，$\red{3}$ 号点所在子树重心编号为 $\red{\{2\}}$，$\red{5}$ 号点所在子树重心编号为 $\red{\{5\}}$。

因此答案为 $\red{1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32}$。

提示

测试点编号	$\red{n=}$	特殊性质
$\red{1\sim 2}$	$\red{7}$	无
$\red{3\sim 5}$	$\red{199}$
$\red{6\sim 8}$	$\red{1999}$
$\red{9\sim 11}$	$\red{49991}$	$\red A$
$\red{12\sim 15}$	$\red{262143}$	$\red B$
$\red{16}$	$\red{99995}$	无
$\red{17\sim 18}$	$\red{199995}$
$\red{19\sim 20}$	$\red{299995}$

表中特殊性质一栏，两个变量的含义为存在一个 $\red{1 \sim n}$ 的排列 $\red{p_i（1 \le i \le n）}$，使得：

• $\red A$：树的形态是一条链。即 $\red{\forall 1 \le i < n}$，存在一条边 $\red{(p_i, p_{i+1})}$。
• $\red B$：树的形态是一个完美二叉树。即 $\red{\forall 1 \le i \le \frac{n-1}{2}}$，存在两条边 $\red{(p_i, p_{2i})}$ 与 $\red{(p_i, p_{2i+1})}$。

对于所有测试点：$\red{1 \le T \le 5 , 1 \le u_i, v_i \le n}$。保证给出的图是一个树。