#2297. 「CSP-S 2019」树的重心 省选/NOI−

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

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

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

上式中， 表示树 的边集， 表示一条连接 号点和 号点的边。 与 分别表示树 删去边 后， 号点与 号点所在的被分裂出的子树， 表示树 重心的集合。

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

从文件 centroid.in 中读入数据。

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

第一行一个整数 表示数据组数。

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

第一行一个整数 表示树 的大小。

接下来 行，每行两个以空格分隔的整数 ，表示树中的一条边 。

输出到文件 centroid.out 中。

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

样例输入 1

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

样例输出 1

32
56

样例说明 1

对于第一组数据：

删去边 ， 号点所在子树重心编号为 ， 号点所在子树重心编号为 。

删去边 ， 号点所在子树重心编号为 ， 号点所在子树重心编号为 。

删去边 ， 号点所在子树重心编号为 ， 号点所在子树重心编号为 。

删去边 ， 号点所在子树重心编号为 ， 号点所在子树重心编号为 。

因此答案为 。

样例 2

见附加文件 centroid2.in/ans。

样例 3

见附加文件 centroid3.in/ans。

该数据满足特殊性质 A，具体信息见数据范围中的描述。

样例 4

见附加文件 centroid4.in/ans。

该数据满足特殊性质 B，具体信息见数据范围中的描述。

表中特殊性质一栏，两个变量的含义为存在一个 的排列 （），使得：

• A：树的形态是一条链。即 ，存在一条边 。
• B：树的形态是一个完美二叉树。即 ，存在两条边 与 。

对于所有测试点：。保证给出的图是一个树。