题目描述
小简单正在学习离散数学,今天的内容是图论基础,在课上他做了如下两条笔记:
一个大小为 n 的树由 n 个结点与 n−1 条无向边构成,且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边,树将分裂为若干个子树;而在树中删去一条边(保留关联结点,下同),树将分裂为恰好两个子树。
对于一个大小为 n 的树与任意一个树中结点 c,称 c 是该树的重心当且仅当在树中删去 c 及与它关联的边后,分裂出的所有子树的大小均不超过 ⌊n/2⌋(其中 ⌊x⌋ 是下取整函数)。对于包含至少一个结点的树,它的重心只可能有 1 或 2 个。
课后老师给出了一个大小为 n 的树 S ,树中结点从 1∼n 编号。小简单的课后作业是求出 S 单独删去每条边后,分裂出的两个子树的重心编号和之和。即:
上式中,E 表示树 S 的边集, (u,v) 表示一条连接 u 号点和 v 号点的边。S′u 与 S′u 分别表示树 S 删去边 (u,v) 后, u 号点与 v 号点所在的被分裂出的子树。
小简单觉得作业并不简单,只好向你求助,请你教教他。
一个大小为 n 的树由 n 个结点与 n−1 条无向边构成,且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边,树将分裂为若干个子树;而在树中删去一条边(保留关联结点,下同),树将分裂为恰好两个子树。
对于一个大小为 n 的树与任意一个树中结点 c,称 c 是该树的重心当且仅当在树中删去 c 及与它关联的边后,分裂出的所有子树的大小均不超过 ⌊n/2⌋(其中 ⌊x⌋ 是下取整函数)。对于包含至少一个结点的树,它的重心只可能有 1 或 2 个。
课后老师给出了一个大小为 n 的树 S ,树中结点从 1∼n 编号。小简单的课后作业是求出 S 单独删去每条边后,分裂出的两个子树的重心编号和之和。即:
上式中,E 表示树 S 的边集, (u,v) 表示一条连接 u 号点和 v 号点的边。S′u 与 S′u 分别表示树 S 删去边 (u,v) 后, u 号点与 v 号点所在的被分裂出的子树。
小简单觉得作业并不简单,只好向你求助,请你教教他。
输入
本题输入包含多组测试数据
第一行一个整数 T 表示数据组数。
接下来依次给出每组输入数据,对于每组数据:
第一行一个整数 n 表示树 S 的大小。
接下来 n−1 行,每行两个以空格分隔的整数 ui,vi ,表示树中的一条边 ui,vi。
第一行一个整数 T 表示数据组数。
接下来依次给出每组输入数据,对于每组数据:
第一行一个整数 n 表示树 S 的大小。
接下来 n−1 行,每行两个以空格分隔的整数 ui,vi ,表示树中的一条边 ui,vi。
输出
共 T 行,每行一个整数,第 i 行的整数表示:第 i 组数据给出的树单独删去每条边后,分裂出的两个子树的重心编号和之和。
样例输入 Copy
2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7
样例输出 Copy
32
56
提示
explanation
对于第一组数据:
删去边 (1,2) , 1 号点所在子树重心编号为 {1}, 2 号点所在子树重心编号为 2,3。
删去边 (2,3) , 2 号点所在子树重心编号为 {2}, 3 号点所在子树重心编号为 3,5。
删去边 (2,4) , 3 号点所在子树重心编号为 {2, 3}, 4 号点所在子树重心编号为 4。
删去边 (3,5) , 3 号点所在子树重心编号为 {2}, 5 号点所在子树重心编号为 5。
因此答案为 1+2+3+2+3+5+2+3+4+2+5=32。
限制与约定
| 测试点编号 | n= | 特殊性质特殊性质 |
|---|---|---|
| 1∼2 | 7 | |
| 3∼5 | 199 | |
| 6∼8 | 1999 | |
| 9∼11 | 49991 | A |
| 12∼15 | 262143 | B |
| 16 | 99995 | |
| 17∼18 | 199995 | |
| 19∼20 | 299995 |
表中表中特殊性质一栏,两个变量的含义为存在一个 1∼n 的排列 pi(1≤i≤n) ,使得:
A:树的形态是一条链。即 ∀1≤i<n,存在一条边 (pi,pi+1)。
B:树的形态是一个完美二叉树。即 ∀1≤i<⌊(n−1)/2⌋ ,存在两条边(pi,p2i) 与 (pi,p2i+1)。
对于所有测试点: 1≤T≤5 , 1≤ui,vi≤n。保证给出的图是一个树。
时间限制: 3s 空间限制: 256MB
关于本题的Hack数据
由于标准算法实际上并不需要利用到数据范围里给定的关于 n 的限制。因此本题的Hack数据中 n 仅需要满足 n∈[7,299995] 且 n 为整数即可，不需要满足题面中的限制。
其余输入条件仍然同题面。