4023: NOIP2019树的重心
Memory Limit：128 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：37
Solved：1
Description
小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：
1. 一个大小为 $n$ 的树由 $n$ 个结点与 $n − 1$ 条无向边构成，且满足任意两个结点间**有且仅有**一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为**恰好**两个子树。
2. 对于一个大小为 $n$ 的树与任意一个树中结点 $c$，称 $c$ 是该树的**重心**当且仅当在树中删去 $c$ 及与它关联的边后，分裂出的所有子树的大小均**不超过** $\\lfloor \\frac{n}{2} \\rfloor$（其中 $\\lfloor x \\rfloor$ 是下取整函数）。对于包含至少一个结点的树，它的重心只可能有 $1$ 或 $2$ 个。
课后老师给出了一个大小为 $n$ 的树 $S$，树中结点从 $1 \\sim n$ 编号。小简单的课后作业是求出 $S$ 单独删去每条边后，分裂出的两个子树的重心编号和之和。即：
$$
\\sum_{(u,v)\\in E}\\left(\\sum_{x\\in c(S_u)} x+\\sum_{y\\in c(S_v)} y\\right)
$$
上式中，$E$ 表示树 $S$ 的边集，$(u, v)$ 表示一条连接 $u$ 号点和 $v$ 号点的边。$S'_u$ 与 $S'_v$ 分别表示树 $S$ 删去边 $(u, v)$ 后，$u$ 号点与 $v$ 号点所在的被分裂出的子树，$c(S)$ 表示树 $S$ 重心的集合。
小简单觉得作业并不简单，只好向你求助，请你教教他。
Input
从文件 `centroid.in` 中读入数据。
**本题输入包含多组测试数据**。
第一行一个整数 $T$ 表示数据组数。
接下来依次给出每组输入数据，对于每组数据：
第一行一个整数 $n$ 表示树 $S$ 的大小。
接下来 $n − 1$ 行，每行两个以空格分隔的整数 $u_i, v_i$，表示树中的一条边 $(u_i, v_i)$。
Output
输出到文件 `centroid.out` 中。
共 $T$ 行，每行一个整数，第 $i$ 行的整数表示：第 $i$ 组数据给出的树单独删去每条边后，分裂出的两个子树的重心编号和之和。
Sample Input Copy
2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7Sample Output Copy
32
56HINT
#### 样例输入 1
```plain
2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7
```
#### 样例输出 1
```plain
32
56
```
#### 样例说明 1
对于第一组数据：
删去边 $(1, 2)$，$1$ 号点所在子树重心编号为 $\\{1\\}$，$2$ 号点所在子树重心编号为 $\\{2, 3\\}$。
删去边 $(2, 3)$，$2$ 号点所在子树重心编号为 $\\{2\\}$，$3$ 号点所在子树重心编号为 $\\{3, 5\\}$。
删去边 $(2, 4)$，$2$ 号点所在子树重心编号为 $\\{2, 3\\}$，$4$ 号点所在子树重心编号为 $\\{4\\}$。
删去边 $(3, 5)$，$3$ 号点所在子树重心编号为 $\\{2\\}$，$5$ 号点所在子树重心编号为 $\\{5\\}$。
因此答案为 $1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32$。
#### 样例 2
见附加文件 `centroid2.in/ans`。
#### 样例 3
见附加文件 `centroid3.in/ans`。
该数据满足特殊性质 A，具体信息见数据范围中的描述。
#### 样例 4
见附加文件 `centroid4.in/ans`。
该数据满足特殊性质 B，具体信息见数据范围中的描述。
| 测试点编号 | $n=$ | 特殊性质 |
| :---------: | :------: | :------: |
| $1\\sim 2$ | $7$ | 无 |
| $3\\sim 5$ | $199$ | 无 |
| $6\\sim 8$ | $1999$ | 无 |
| $9\\sim 11$ | $49991$ | A |
| $12\\sim 15$ | $262143$ | B |
| $16$ | $99995$ | 无 |
| $17\\sim 18$ | $199995$ | 无 |
| $19\\sim 20$ | $299995$ | 无 |
表中特殊性质一栏，两个变量的含义为存在一个 $1 \\sim n$ 的排列 $p_i$（$1 \\le i \\le n$），使得：
- A：树的形态是一条链。即 $\\forall 1 \\le i < n$，存在一条边 $(p_i, p_{i+1})$。
- B：树的形态是一个完美二叉树。即 $\\forall 1 \\le i \\le \\frac{n-1}{2}$，存在两条边 $(p_i, p_{2i})$ 与 $(p_i, p_{2i+1})$。
对于所有测试点：$1 \\le T \\le 5 , 1 \\le u_i, v_i \\le n$。保证给出的图是一个树。