P7165

传送门。 题意 有一棵树，可以断掉 \(2\) 条边，会形成三个连通块，求三个连通块中大小最大减最小的最小值。 分析 我们观察两条边之间的关系，分类考虑： 两条边成祖孙关系。 两条边没有祖孙关系。 首先，我们肯定我们的大方向，固一动一（说起来为什么想到了数学题），先固定一条边，再在其他边中取得最适合 ......

### 题面描述 给定一颗树，求分成三部分后的最小差异值。 ### 题解 暴力：每次枚举两个点，将其父边断掉，如果存在祖先关系则特判一下，复杂度 $O(n^2)$，预计 50pts。 正解：dfs 搜索每个结点，砍掉它的父边，剩下的尽量等分（易证）。 这一步可以用 multiset 维护。 对于一个 ......