papricice
阅读原文时间:2023年08月22日阅读:2

2023-07-14

题目传送门

题目大意

给定一个 \(n\) 个点的树,这 \(n\) 个点编号为 \(1\) 到 \(n\)。

现在要选择断掉两条边,会形成三个连通块,假设这三个连通块内的点数分别为 \(a,b,c\),那么您要做的就是最小化 \(\max\{a,b,c\}-\min\{a,b,c\}\) 的大小,求这个最小值。

难度&重要性(1~10):6

题目来源

COCI,luogu

STL

由于要切两刀,我们可以考虑先枚举 \(i\) 切断点 \(i\) 与其父节点的连边,再去找另一条边。

这里我们这知道,由于一条边已经定下,另一条边当然是切得越平均越好。

设切断节点 \(j\) 与其父节点的连边,\(siz_x\) 为以节点 \(x\) 为根的子树大小。

考虑两种情况:

  • 如果节点 \(j\) 是节点 \(i\) 的祖先,那么三棵树的大小就为 \(siz_i,siz_j-siz_i,n-siz_i-siz_j\)。
  • 如果节点 \(j\) 不是节点 \(i\) 的祖先,那么三棵树的大小就为 \(siz_i,siz_j,n-siz_i-siz_j\)。

因为需要第二条边切的尽量平均,则越接近 \(\frac{n-siz_i}{2}\) 越好,这里我们就可以用 set 来维护它的前驱后继来得到答案。

已完成

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章