题目翻译

E2. 距离树（困难版）
给定一棵 $n$ 个节点的树，每条边的权值为 $1$。记 $d(v)$ 为节点 $1$ 到节点 $v$ 的距离。
你可以临时在任意两个节点 $a,b$ 之间添加一条权值为 $x$ 的边（添加后图不再是树）。定义 $f(x)$ 为添加这条边后，$\max_{1\le v\le n} d(v)$ 可能的最小值。
对每个 $x = 1,2,\dots,n$，求出 $f(x)$。

---

题解思路

1. 基本观察

• 以 $1$ 为根，记 $\text{dep}[v]$ 为原树中 $1$ 到 $v$ 的距离（即深度）。
• 添加一条边后，从 $1$ 到 $v$ 的新距离为 $\min(\text{dep}[v],\ \text{经过新边的路径长度})$。
• 若某节点的深度已经 $\le \text{ans}$，则无需考虑；否则需要利用新边缩短距离。
• 设 $S_{\text{ans}} = \{v \mid \text{dep}[v] > \text{ans}\}$，并记 $L_{\text{ans}}$ 为 $S_{\text{ans}}$ 中任意两点在原树中的最大距离（直径）。若 $S_{\text{ans}}$ 为空，则 $L_{\text{ans}}=0$。

2. 可行性判定

对于固定的 $\text{ans}$，如果存在一条权值为 $x$ 的边，使得新图中从 $1$ 出发的最远距离 $\le \text{ans}$，则必须满足：

• 要么 $\text{ans} \ge \max \text{dep}$（此时无需加边）；
• 要么 $\left\lceil \dfrac{L_{\text{ans}}}{2} \right\rceil + x \le \text{ans}$。

解释：最优加边策略是连接 $1$ 与 $S_{\text{ans}}$ 的“中心”（直径中点），这样从 $1$ 到 $S_{\text{ans}}$ 中任意点的距离不超过 $x + \lceil L_{\text{ans}}/2\rceil$。因此，当 $x \le \text{ans} - \lceil L_{\text{ans}}/2\rceil$ 时，$\text{ans}$ 可行。

3. 计算 $L_{\text{ans}}$ 数组

我们需要对每个 $\text{ans}=0,1,\dots,n-1$ 求出 $L_{\text{ans}}$。
使用树形 DP：

• 第一次 DFS 计算 $\text{dep}[v]$。
• 第二次 DFS 后序遍历，计算 $\text{down}[v]$：从 $v$ 向下走到最深叶子的边数。

$$ \text{down}[v] = \max_{c \in \text{children}(v)} (1 + \text{down}[c]) \quad (\text{若没有孩子则为 }0) $$

• 对于每个节点 $v$，收集所有孩子 $c$ 的 $(1+\text{down}[c])$，取出最大值 $h_1$ 和次大值 $h_2$（不足则补 $0$）。
  这两条链的端点深度分别为 $\text{dep}[v]+h_1$ 和 $\text{dep}[v]+h_2$，它们的距离为 $h_1+h_2$。
  该距离对阈值 $\text{ans}$ 有贡献当且仅当 $\text{ans} < \min(\text{dep}[v]+h_1,\ \text{dep}[v]+h_2)$，即 $\text{ans} \le \min(\dots)-1$。
  令 $\text{lim} = \min(\text{dep}[v]+h_1,\ \text{dep}[v]+h_2)-1$，若 $\text{lim}\ge 0$，则

$$ \text{best}[\text{lim}] = \max(\text{best}[\text{lim}],\ h_1+h_2) $$

• 处理完所有节点后，对 $\text{best}$ 数组从大到小做后缀最大值：

$$ \text{for } i = n-2 \text{ down to } 0:\ \text{best}[i] = \max(\text{best}[i],\ \text{best}[i+1]) $$

此时 $\text{best}[\text{ans}]$ 即为 $L_{\text{ans}}$。

4. 由 $L_{\text{ans}}$ 得到 $f(x)$

记 $T_{\text{ans}} = \text{ans} - \left\lceil \dfrac{L_{\text{ans}}}{2} \right\rceil$。
对于固定的 $x$，最小的可行 $\text{ans}$ 就是满足 $T_{\text{ans}} \ge x$ 的最小 $\text{ans}$（若不存在则取 $\max \text{dep}$）。
由于 $T_{\text{ans}}$ 随 $\text{ans}$ 单调不减，可以用双指针：

• 初始化 $\text{ans}=0$，结果数组 $\text{res}[1..n]$ 全部设为 $\max\text{dep}$。
• 对 $x$ 从 $1$ 到 $n$：
  • 当 $\text{ans} \le \max\text{dep}$ 且 $T_{\text{ans}} < x$ 时，$\text{ans} \leftarrow \text{ans}+1$。
  • 若 $\text{ans} \le \max\text{dep}$，则 $\text{res}[x] = \text{ans}$；否则 $\text{res}[x] = \max\text{dep}$。

最后输出 $\text{res}[1], \text{res}[2], \dots, \text{res}[n]$。

5. 复杂度

• DFS 两次 $O(n)$
• 计算 $\text{best}$ 数组 $O(n)$
• 后缀最大值 $O(n)$
• 双指针 $O(n)$
  总时间复杂度 $O(n)$，空间复杂度 $O(n)$。

---

示例验证

以第一个测试用例为例：

• $n=4$，树边：1-2, 2-3, 1-4
• 计算得 $\text{dep}=[0,1,2,1]$，$\max\text{dep}=2$
• 得到 $L_0=3,\ L_1=0,\ L_2=0$
• $T_0=-2,\ T_1=1,\ T_2=2$
• 双指针：
  • $x=1$：$T_0<1$ → $\text{ans}=1$，$T_1=1\ge1$ → $\text{res}[1]=1$
  • $x=2$：$T_1=1<2$ → $\text{ans}=2$，$T_2=2\ge2$ → $\text{res}[2]=2$
  • $x=3,4$：$\text{ans}>2$ → $\text{res}=2$
• 输出 1 2 2 2，与样例一致。

---

代码实现要点

• 使用邻接表存图。
• DFS 可用栈迭代避免递归深度过大。
• 注意数组下标从 $0$ 开始，$\text{best}$ 大小设为 $n+2$。
• 计算 $\lceil L/2\rceil$ 可用 (L+1)/2。