Description

小简单正在学习离散数学,今天的内容是图论基础,在课上他做了如下两条笔记:
    1. 一个大小为 nn 的树由 nn 个结点与 n1n − 1 条无向边构成,且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边,树将分裂为若干个子树;而在树中删去一条边(保留关联结点,下同),树将分裂为恰好两个子树。
    2. 对于一个大小为 nn 的树与任意一个树中结点 cc,称 cc 是该树的重心当且仅当在树中删去 cc 及与它关联的边后,分裂出的所有子树的大小均不超过 n2⌊\frac{n}{2}⌋ (其中 x⌊x⌋ 是下取整函数)。对于包含至少一个结点的树,它的重心只可能有 1122 个。
    课后老师给出了一个大小为 nn 的树 SS ,树中结点从 1n1 ∼ n 编号。小简单的课后作业是求出 SS 单独删去每条边后,分裂出的两个子树的重心编号和之和。即:
enter image description here
    上式中,EE 表示树 SS 的边集,(u,v)(u, v) 表示一条连接 uu 号点和 vv 号点的边。SuS_{u}^{′}SvS_{v}^{′} 分别表示树 SS 删去边 (u,v)(u, v) 后,uu 号点与 vv 号点所在的被分裂出的子树。
    小简单觉得作业并不简单,只好向你求助,请你教教他。

Input

本题输入包含多组测试数据。
    第一行一个整数 TT 表示数据组数。
    接下来依次给出每组输入数据,对于每组数据:
    第一行一个整数 nn 表示树 SS 的大小。
    接下来 n1n − 1 行,每行两个以空格分隔的整数 uiu_i, viv_i,表示树中的一条边 (ui,vi)(u_i, v_i)

Output

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

Sample Input
2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7
Sample Output
32
56
Hint

【样例解释】
    对于第一组数据:
    删去边 (1,2)(1, 2)11 号点所在子树重心编号为 {1}\{1\}22 号点所在子树重心编号为 {2,3}\{2, 3\}
    删去边 (2,3)(2, 3)22 号点所在子树重心编号为 {2}\{2\}33 号点所在子树重心编号为 {3,5}\{3, 5\}
    删去边 (2,4)(2, 4)22 号点所在子树重心编号为 {2,3}\{2, 3\}44 号点所在子树重心编号为 {4}\{4\}
    删去边 (3,5)(3, 5)33 号点所在子树重心编号为 {2}\{2\}55 号点所在子树重心编号为 {5}\{5\}
    因此答案为 1+2+3+2+3+5+2+3+4+2+5=321 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32
    【数据范围】
enter image description here
    表中特殊性质一栏,两个变量的含义为存在一个 1n1 ∼ n 的排列 pi(1in)p_i(1 ≤ i ≤ n),使得:
    AA:树的形态是一条链。即 1i<n∀1 ≤ i < n,存在一条边 (pi,pi+1)(p_i, p_{i+1})
    BB:树的形态是一个完美二叉树。即 1in12∀1 ≤ i ≤ \frac{n-1}{2},存在两条边 (pi,p2i)(p_i, p_{2i})(pi,p2i+1)(p_i, p_{2i+1})
    对于所有测试点:1T51 ≤ T ≤ 5 , 1ui,vin1 ≤ u_i, v_i ≤ n。保证给出的图是一个树。