HBC54640优美字符串,枚举[CSP2019]树的重心（centroid）题解

痛心疾首算法基础篇 2023-11-13 12:41:02 58 0

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

已替换官方数据小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：一个大小为 n 的树由 n 个结点与 n 1 条无向边构成，且满足任意两个结点间有且仅有一条简单路径，在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树对于一个大小为 n 的树与任意一个树中结点 c，称 c

已替换官方数据小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：一个大小为 n 的树由 n 个结点与 n − 1 条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树对于一个大小为 n 的树与任意一个树中结点 c，称 c 是该树的重心当且仅当在树中删去 c 及与它关联的边后，分裂出的所有子树的大小均不超过⌊n2⌋displaystylelfloor frac{n}{2} rfloor⌊2n⌋，（其中⌊x⌋lfloor x rfloor⌊x⌋）。对于包含至少一个结点的树，它的重心只可能有 1 或 2 个。课后老师给出了一个大小为 n 的树 S，树中结点从 1 ∼ n 编号。小简单的课后作业是求出 S 单独删去每条边后，分裂出的两个子树的重心编号和之和。即： ∑(u,v)∈E(∑1≤x≤n, 且x号点是Su′的重心x +∑1≤y≤n, 且y号点是Sv′的重心y)displaystylesum_{(u, v) in E}left( sum_{1 leq x leq n, text{且}xtext{号点是}S^{prime}_utext{的重心}} x +sum_{1 leq y leq n, text{且}ytext{号点是}S^{prime}_vtext{的重心}} yright)(u,v)∈E∑⎝⎛1≤x≤n, 且x号点是Su′的重心∑x +1≤y≤n, 且y号点是Sv′的重心∑y⎠⎞ 上式中， E 表示树 S 的边集， (u, v) 表示一条连接 u 号点和 v 号点的边。Su′S^{prime}_uSu′与Sv′S^{prime}_vSv′分别表示树 S 删去边 (u, v) 后， u 号点与 v 号点所在的被分裂出的子树。小简单觉得作业并不简单，只好向你求助，请你教教他。