给定一个 \(n\) 个点的树,这 \(n\) 个点编号为 \(1\) 到 \(n\)。
现在要选择断掉两条边,会形成三个连通块,假设这三个连通块内的点数分别为 \(a,b,c\),那么您要做的就是最小化 \(\max\{a,b,c\}-\min\{a,b,c\}\) 的大小,求这个最小值。
COCI,luogu
STL
由于要切两刀,我们可以考虑先枚举 \(i\) 切断点 \(i\) 与其父节点的连边,再去找另一条边。
这里我们这知道,由于一条边已经定下,另一条边当然是切得越平均越好。
设切断节点 \(j\) 与其父节点的连边,\(siz_x\) 为以节点 \(x\) 为根的子树大小。
考虑两种情况:
因为需要第二条边切的尽量平均,则越接近 \(\frac{n-siz_i}{2}\) 越好,这里我们就可以用 set 来维护它的前驱后继来得到答案。
已完成
手机扫一扫
移动阅读更方便
你可能感兴趣的文章