题解：加边后最小化直径

问题转化

给定一棵 $n$ 个节点的树（边权为正），需要加一条长度为 $L$ 的边（连接任意两个节点）。
新图的直径定义为任意两点最短路的最大值。
要求选择加边的两个端点，使得新图的直径最小，输出这个最小直径。

关键观察

1. 加边对路径的影响

设加的边连接 $u$ 和 $v$，边权为 $L$。
新图中任意两点 $x,y$ 的最短路为：

$$\min(\text{dist}_T(x,y),\ \text{dist}_T(x,u)+L+\text{dist}_T(v,y),\ \text{dist}_T(x,v)+L+\text{dist}_T(u,y)) $$

其中 $\text{dist}_T$ 表示树上的距离。

2. 直径候选

新图的直径可能来自：

• 原树的直径（不加这条边时已经最大）
• 经过新边的某条路径

设原树直径为 $D$，则新图直径至少为 $D$（因为加边不会使原来最远的点对变近）。
但加边后可能产生更长的路径，所以我们要最小化的是 $\max(D, \text{经过新边的最长路径})$。

3. 经过新边的最长路径

考虑新边连接 $u,v$，经过新边的最长路径为：

$$\max_{x} \text{dist}_T(x,u) + L + \max_{y} \text{dist}_T(v,y) $$

但 $x$ 和 $y$ 可以相同，所以实际上是：

$$\max_{x,y} [\text{dist}_T(x,u) + L + \text{dist}_T(v,y)] $$

这等于：

$$\text{depth}_u + L + \text{depth}_v$$

其中 $\text{depth}_u = \max_x \text{dist}_T(x,u)$ 是 $u$ 到最远点的距离（即 $u$ 的偏心距）。

所以经过新边的最长路径为 $\text{ecc}(u) + L + \text{ecc}(v)$，其中 $\text{ecc}(x)$ 表示 $x$ 的偏心距。

4. 问题简化

我们需要选择 $u,v$，使得：

$$\max(D,\ \text{ecc}(u)+L+\text{ecc}(v))$$

最小。

令 $A = \min_{u,v} [\text{ecc}(u)+L+\text{ecc}(v)]$，则答案为 $\max(D, A)$。

但注意 $u,v$ 是加边的两个端点，$\text{ecc}(u)+L+\text{ecc}(v)$ 的最小值可能小于 $D$，此时答案就是 $D$。

实际上，我们是要最小化：

$$\min_{u,v} \max(D,\ \text{ecc}(u)+L+\text{ecc}(v)) $$

这等价于：找到最小的 $t$，使得存在 $u,v$ 满足 $\text{ecc}(u)+L+\text{ecc}(v) \le t$ 且 $D \le t$。

因为 $D$ 是固定的，所以 $t \ge D$。
问题变为：是否存在 $u,v$ 使得 $\text{ecc}(u)+\text{ecc}(v) \le t - L$。

5. 二分答案

二分最终的直径 $ans$，检查是否存在 $u,v$ 使得：

1. $\text{ecc}(u) + \text{ecc}(v) + L \le ans$（保证经过新边的路径不超过 $ans$）
2. 并且原树中所有点对距离不超过 $ans$（这一条自动满足，因为 $ans \ge D$）

所以只需检查条件1。

6. 检查方法

对于给定的 $ans$，需要判断是否存在 $u,v$ 使得 $\text{ecc}(u) + \text{ecc}(v) \le ans - L$。

这相当于在偏心距数组 $\text{ecc}[1..n]$ 中找两个数，它们的和不超过 $T = ans - L$。

可以排序 $\text{ecc}$ 数组，然后用双指针检查。时间复杂度 $O(n \log n)$。

但需要 $O(n)$ 预处理所有点的偏心距。

7. 计算偏心距

偏心距 $\text{ecc}(u) = \max_{v} \text{dist}(u,v)$。

可以通过两次 DFS 求出树的直径端点 $p,q$，然后对于任意点 $u$：

$$\text{ecc}(u) = \max(\text{dist}(u,p),\ \text{dist}(u,q)) $$

证明：树的直径端点一定包含离 $u$ 最远的点之一。

所以：

1. DFS 从任意点（如1）找到最远点 $p$
2. DFS 从 $p$ 找到最远点 $q$，同时记录 $distP[u] = \text{dist}(p,u)$
3. DFS 从 $q$ 记录 $distQ[u] = \text{dist}(q,u)$
4. $\text{ecc}[u] = \max(distP[u], distQ[u])$

8. 算法步骤

1. 读入 $n, L$，若 $n=0$ 结束
2. 读入树，建立邻接表
3. 求直径端点 $p,q$，并计算 $distP[u], distQ[u]$
4. 计算 $D = distP[q]$（即直径长度）
5. 计算 $\text{ecc}[u] = \max(distP[u], distQ[u])$
6. 对 $\text{ecc}$ 数组排序
7. 二分答案 $ans$，下界 $D$，上界 $D + 2L$（因为加边最多使直径增加 $2L$） 对于每个 $ans$：
   • $T = ans - L$
   • 若 $T < 0$，则不可能，需要增大 $ans$
   • 否则检查是否存在 $i < j$ 使得 $\text{ecc}[i] + \text{ecc}[j] \le T$ 用双指针：固定 $i$，找最大的 $j$ 使得和 $\le T$，由于数组已排序，只需 $O(n)$ 扫描
8. 输出最小的满足条件的 $ans$

9. 时间复杂度

• 预处理：$O(n)$
• 排序：$O(n \log n)$
• 二分：$O(\log L) \times O(n)$ 总复杂度 $O(n \log n + n \log L)$，可过 $n \le 10^5$。

10. 注意事项

• 多组数据，注意清空数组
• 边权可能很大，用 long long
• 二分上界可以设为 $D + 2L$，但更安全地设为 $D + 2L + 1$
• 检查时注意 $u,v$ 可以是同一个点吗？加边需要两个不同端点，所以 $i \neq j$

11. 检查优化

对于每个 $T$，检查是否存在两个不同点的偏心距和 $\le T$：

• 排序后，设 $i=1,j=n$
• 若 $\text{ecc}[1] + \text{ecc}[2] > T$，则无解（因为最小的两个和已经大于 $T$）
• 否则，用双指针从两端向中间扫描： 若 $\text{ecc}[i] + \text{ecc}[j] \le T$，则存在解（取 $i$ 和 $j$ 对应的点） 否则 $j$--

实际上因为要 $i \neq j$，且两点不同即可，可以直接检查最小的两个和是否 $\le T$，因为如果最小的两个和都大于 $T$，其他组合更大。
但需要确保这两个点不同，如果 $n=1$ 则不行（但 $n \ge 1$，加边需要两个点，所以 $n \ge 2$）。

所以检查可以简化为：若 $\text{ecc}[1] + \text{ecc}[2] \le T$，则有解。

但这是充分条件吗？考虑我们要找两个点 $u,v$，它们的偏心距和 $\le T$，排序后最小的两个和确实是所有组合中最小的，所以如果它俩和大于 $T$，其他组合更大，无解。

因此检查是 $O(1)$ 的。

12. 最终算法

1. 预处理 $\text{ecc}$ 数组
2. 排序 $\text{ecc}$
3. 二分 $ans$ 从 $D$ 到 $D+2L$
4. 检查 $\text{ecc}[1] + \text{ecc}[2] \le ans - L$
5. 输出最小 $ans$

但注意：$\text{ecc}[1]$ 和 $\text{ecc}[2]$ 可能对应同一个点吗？不会，因为它们是不同点的偏心距。

13. 边界情况

• $L=0$：加边长度为0，相当于不加边，答案 $D$
• 树是一条链：加边可以缩短某些距离，但直径可能不变
• $n=2$：只有一条边，加边后成环

总结

算法核心：

1. 求树的直径 $D$ 和每个点的偏心距 $\text{ecc}[u]$
2. 排序 $\text{ecc}$
3. 二分答案 $ans$，检查 $\text{ecc}[1]+\text{ecc}[2] \le ans-L$
4. 输出 $ans$