题目理解

我们有一棵 $n$ 个节点的树，要切掉两条边，把树分成三个连通块。设它们的大小分别为 $a, b, c$（$a+b+c=n$），我们要最小化：

$$\max(a,b,c) - \min(a,b,c)$$

核心思路

1. 切割的两种情况

在树上切两条边后，形成的三个连通块可以表示为：

• $x$：第一条边下方的子树大小
• $y$：第二条边下方的子树大小
• $n-x-y$：剩下的部分

根据两条边的位置关系，有两种情况：

情况1：两条边在一条链上（祖先-后代关系）

• 假设先切靠近根的边，再切它下方的边
• 三部分为：$y$, $x-y$, $n-x$
• 其中 $y < x$（因为 $y$ 在 $x$ 内部）

情况2：两条边不在一条链上

• 三部分为：$x$, $y$, $n-x-y$
• $x$ 和 $y$ 互不包含

2. 问题转化

对于任意切割方式，三个连通块的大小都可以表示为：

$$x,\ y,\ n-x-y$$

其中 $x$ 和 $y$ 是某两条边对应的子树大小。

我们的目标是选择 $x$ 和 $y$，使得：

$$\max(x, y, n-x-y) - \min(x, y, n-x-y)$$

最小。

3. 枚举策略

步骤1：预处理

• 通过DFS计算每个节点的子树大小 $sz[u]$
• 每个节点对应一条"父边"，该边下方的子树大小就是 $sz[u]$

步骤2：处理情况1（两条边在一条链上）

对于每个可能的 $x$（即某个子树大小）：

• 在 $x$ 对应的子树内部，寻找一个 $y$（即 $x$ 的某个子孙子树大小）
• 使得 $y$, $x-y$, $n-x$ 三个数尽可能接近
• 最优的 $y$ 应该接近 $\frac{x}{2}$，但要考虑 $n-x$ 的影响

实现方法：

• 对每个节点维护它子树内所有可能的子树大小集合
• 对于给定的 $x$，在集合中二分查找最合适的 $y$

步骤3：处理情况2（两条边不在一条链上）

对于每个可能的 $x$：

• 在整棵树中寻找一个 $y$，且 $y$ 不在 $x$ 的子树内
• 使得 $x$, $y$, $n-x-y$ 三个数尽可能接近
• 最优的 $y$ 应该接近 $\frac{n-x}{2}$

实现方法：

• 维护全局的子树大小集合
• 对于每个 $x$，从全局集合中移除 $x$ 子树内的所有子树大小
• 在剩余集合中二分查找最合适的 $y$

4. 算法优化

时间复杂度优化：

• 直接枚举所有 $(x,y)$ 是 $O(n^2)$，不可行
• 使用DFS + 启发式合并：
  • 每个节点维护一个multiset，存储它子树内所有可能的子树大小
  • 合并时，小的集合合并到大的集合中
  • 总时间复杂度 $O(n \log^2 n)$

查找优化：

• 对于给定的目标值 $target$，在集合中：
  • 找到 $\ge target$ 的最小值
  • 找到 $\le target$ 的最大值
  • 检查这两个候选值哪个能产生更优解

5. 关键观察

1. 平衡思想：理想情况下，三个连通块大小都接近 $\frac{n}{3}$
2. 单调性：固定 $x$ 后，随着 $y$ 增加，三个数的分布有规律变化
3. 边界处理：要确保 $n-x-y > 0$，即 $x+y < n$

6. 算法流程

1. DFS计算所有子树大小
2. 第二次DFS：
   • 对于每个节点，处理情况1（在子树内找第二条边）
   • 合并子树信息（启发式合并）
   • 将当前子树大小加入集合
3. 第三次DFS（或与第二步结合）：
   • 对于每个节点，处理情况2（在子树外找第二条边）
   • 动态维护全局可用子树大小集合

总结

这道题的核心在于：

• 将问题转化为寻找两个合适的子树大小 $x$ 和 $y$
• 利用数据结构和二分查找优化枚举过程
• 通过启发式合并控制时间复杂度

最终能在 $O(n \log^2 n)$ 时间内解决 $n \le 2\times 10^5$ 的数据规模。