小简单正在学习离散数学,今天的内容是图论基础,在课上他做了如下两条笔记:
- 一个大小为
的树由 个结点与 条无向边构成,且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边,树将分裂为若干个子树;而在树中删去一条边(保留关联结点,下同),树将分裂为恰好两个子树。 - 对于一个大小为 n 的树与任意一个树中结点
,称 是该树的重心当且仅当在树中删去 及与它关联的边后,分裂出的所有子树的大小均不超过 (其中 是下取整函数)。对于包含至少一个结点的树,它的重心只可能有 1 或 2 个。
课后老师给出了一个大小为
上式中,
小简单觉得作业并不简单,只好向你求助,请你教教他。
输入格式
本题输入包含多组测试数据
第一行一个整数
接下来依次给出每组输入数据,对于每组数据:
第一行一个整数
接下来
输出格式
共
样例1
input
2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7
output
32
56
explanation
对于第一组数据:
删去边
删去边
删去边
删去边
因此答案为
限制与约定
测试点编号 | ||
---|---|---|
表中特殊性质一栏,两个变量的含义为存在一个
A:树的形态是一条链。即
B:树的形态是一个完美二叉树。即
对于所有测试点:
时间限制:
空间限制:
关于本题的Hack数据
由于标准算法实际上并不需要利用到数据范围里给定的关于
其余输入条件仍然同题面。