树的重心

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

1.一个大小为n的树由n个结点与n-1条无向边构成，且满足任意两个结点间有 且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个 子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。

2.对于一个大小为n的树与任意一个树中结点c,称c是该树的重心当且仅当在树 中删去c及与它关联的边后，分裂出的所有子树的大小均不超过（其中Lx」 是下取整函数）。对于包含至少一个结点的树.它的重心只可能有1或2个。

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

上式中，E表示树S的边集，（u，n）表示一条连接u号点和V号点的边。S'u与S'v 分别表示树S删去边（u，v）后，u号点与V号点所在的被分裂出的子树。

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

【输入格式】

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

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

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

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

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

接下来n -1行，每行两个以空格分隔的整数 ui，vi，表示树中的一条边（ui，vi）。

【输出格式】

输出到文件centroid.out中。

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

【样例1输入】

2

5

12

23

24

35

7

1 2

1 3

1 4

3 5

3 6

6 7

【样例1输出】

32

56

【样例1解释】

对于第一组数据:

删去边（1,2）, 1号点所在子树重心编号为｛1｝, 2号点所在子树重心编号为｛2,3｝。 删去边（2,3）, 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。

【数据范围】

表中特殊性质一栏，两个变量的含义为存在一个1~n的排列使得: 

A：树的形态是一条链。即存在一条边(pi,pi+1)。

B：树的形态是一个完美二叉树。即存在两条边(Pi，P2i)与(Pi，P2i+1)。 对于所有测试点：保证给岀的图是一个树。