题解：高速公路网络优化

问题分析

我们有一棵 $n$ 个节点的树（原高速公路网络），可以删除一条边并添加一条新边（保证仍是树），目标是：

• 乐观方案：最小化新树的直径（最长路径的边数）
• 悲观方案：最大化新树的直径

核心思想

树的重构与直径性质：
删除树的一条边 $(u,v)$ 会将其分成两棵子树 $T_u$ 和 $T_v$，添加新边 $(x,y)$ 相当于在两棵子树间建立连接。新树的直径由三部分决定：

1. $T_u$ 的直径
2. $T_v$ 的直径
3. 跨过新边的最长路径：$T_u$ 中离 $x$ 最远的点到 $T_v$ 中离 $y$ 最远的点

关键算法

1. 预处理

• DFS 序与 LCA：通过 DFS 记录每个节点的进入/离开时间，并建立 ST 表求 LCA
• 子树直径：用树形 DP 计算每个节点的子树直径（最远点对）
• 前缀/后缀直径：对 DFS 序做前缀和后缀合并，快速求除去某子树后的剩余部分直径

2. 枚举断边

对于每条边 $(i, fa[i])$：

• $T_1$ = 以 $i$ 为根的子树
• $T_2$ = 剩余部分

3. 乐观方案

最小化：

$$\max(\text{diam}(T_1), \text{diam}(T_2), \lceil\frac{\text{diam}(T_1)}{2}\rceil + \lceil\frac{\text{diam}(T_2)}{2}\rceil + 1) $$

选择两棵子树的中心点（直径中点）连接。

4. 悲观方案

最大化：

$$\text{diam}(T_1) + \text{diam}(T_2) + 1$$

选择两棵子树的直径端点连接。

复杂度分析

• 时间复杂度：$O(n \log n)$，主要来自 LCA 预处理
• 空间复杂度：$O(n \log n)$，用于 ST 表存储

算法优势

1. 完整性：枚举所有可能的断边，保证找到最优解
2. 高效性：通过预处理在 $O(1)$ 时间内计算任意子树的直径
3. 正确性：基于树直径的性质，数学推导出最优连接策略