#CSPS2019F. 树的重心(centroid)
树的重心(centroid)
题目描述
小简单正在学习离散数学,今天的内容是图论基础,在课上他做了如下两条笔记:
-
一个大小为 的树由 个结点与 条无向边构成,且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边,树将分裂为若干个子树;而在树中删去一条边(保留关联结点,下同),树将分裂为恰好两个子树。
-
对于一个大小为 的树与任意一个树中结点 ,称 是该树的重心当且仅当在树中删去 及与它关联的边后,分裂出的所有子树的大小均不超过 (其中 是下取整函数)。对于包含至少一个结点的树,它的重心只可能有 或 个。
课后老师给出了一个大小为 的树 ,树中结点从 编号。小简单的课后作业是求出 单独删去每条边后,分裂出的两个子树的重心编号和之和。即:
$$\sum_{(u,v)\in E}\left(\sum_{x\in c(S'_u)} x+\sum_{y\in c(S'_v)} y\right) $$上式中, 表示树 的边集, 表示一条连接 号点和 号点的边。 与 分别表示树 删去边 后, 号点与 号点所在的被分裂出的子树, 表示树 重心的集合。
小简单觉得作业并不简单,只好向你求助,请你教教他。
输入格式
从文件 centroid.in
中读入数据。
本题输入包含多组测试数据。
第一行一个整数 表示数据组数。
接下来依次给出每组输入数据,对于每组数据:
第一行一个整数 表示树 的大小。
接下来 行,每行两个以空格分隔的整数 ,表示树中的一条边 。
输出格式
输出到文件 centroid.out
中。
共 行,每行一个整数,第 行的整数表示:第 组数据给出的树单独删去每条边后,分裂出的两个子树的重心编号和之和。
2
5
1 2
2 3
2 4
3 5
7
1 2
1 3
1 4
3 5
3 6
6 7
32
56
样例说明 1
对于第一组数据:
删去边 , 号点所在子树重心编号为 , 号点所在子树重心编号为 。
删去边 , 号点所在子树重心编号为 , 号点所在子树重心编号为 。
删去边 , 号点所在子树重心编号为 , 号点所在子树重心编号为 。
删去边 , 号点所在子树重心编号为 , 号点所在子树重心编号为 。
因此答案为 。
样例 2
见附加文件 centroid2.in、centroid2.ans。
样例 3
见附加文件 centroid3.in、centroid3.ans。
该数据满足特殊性质 A,具体信息见数据范围中的描述。
样例 4
见附加文件 centroid4.in、centroid4.ans。
该数据满足特殊性质 B,具体信息见数据范围中的描述。
数据范围与提示
测试点编号 | 特殊性质 | |
---|---|---|
无 | ||
A | ||
B | ||
无 | ||
表中特殊性质一栏,两个变量的含义为存在一个 的排列 (),使得:
- A:树的形态是一条链。即 ,存在一条边 。
- B:树的形态是一个完美二叉树。即 ,存在两条边 与 。
对于所有测试点:,。保证给出的图是一个树。