---

一、题目核心理解

• 给一棵 $n$ 个节点的树，边有权重 $w_i$。
• 定义 $dist(u,v)$ 为树上唯一路径的边权和。
• 最重要的两个城市是 $1$ 和 $n$（代码中编号为 $0$ 和 $n-1$）。
• 我们可以添加一条长度为 $x$ 的新边 $(u,v)$（$u \ne v$，且原来没有直接边），使得 $dist(1, n)$ 尽可能大。
• 对于每个询问的 $x$，输出最大可能的 $dist(1,n)$。

---

二、关键观察

1. 原树中 $dist(1,n)$ 是固定的

设 $cur = dist(1,n)$，这是不添加任何边时的距离。

2. 添加一条边的影响

添加边 $(u,v)$ 后，新图中 $1$ 到 $n$ 的最短路径会变成：

$$\min( cur,\ dist(1,u) + x + dist(v,n),\ dist(1,v) + x + dist(u,n) ) $$

因为新边提供了一条“捷径”。

为了使 $dist(1,n)$ 尽量大，我们希望新路径不要比原路径短太多，甚至希望新路径更长（但不会，因为 $x \ge 1$ 且新路径往往更短）。

实际上，添加一条边只会让 $dist(1,n)$ 减小或不变（因为提供了更短的可能路径）。
但题目要求最大化 $dist(1,n)$，所以我们要让这个缩短量尽可能小。

---

三、转化为求最小缩短量

设 $f(u,v) = \min( dist(1,u) + x + dist(v,n),\ dist(1,v) + x + dist(u,n) )$。

添加边后 $dist(1,n) = \min( cur,\ f(u,v) )$。

我们希望这个值最大，即希望 $f(u,v)$ 尽可能接近 $cur$（但不会超过 $cur$）。

定义缩短量：

$$\Delta(u,v) = cur - f(u,v)$$

我们要最小化 $\Delta(u,v)$（因为 $cur$ 固定）。

当 $x$ 变化时，最优的 $(u,v)$ 可能不同。

---

四、化简 $\Delta(u,v)$

设 $d_u = dist(1,u)$，$d'_u = dist(u,n)$。

注意：$d_u + d'_u = cur$ 当且仅当 $u$ 在 $1 \to n$ 的路径上。
对于不在该路径上的点，$d_u + d'_u > cur$。

我们考虑 $u$ 和 $v$ 的四种情况，但对称性可简化为：

$$f(u,v) = \min( d_u + x + d'_v,\ d_v + x + d'_u )$$

我们希望这个最小值尽量大，即尽量接近 $cur$。

---

五、关键结论（来自代码）

代码中定义：

• $dif$：最小可能的缩短量（与 $x$ 无关的部分）
• 最终答案：$\min(cur,\ cur - dif + x)$

为什么？
因为最优的 $\Delta(u,v)$ 可以写成 $dif - x$ 的形式，其中 $dif$ 是某个与 $x$ 无关的常数（由树结构决定）。
于是：

$$f(u,v) = cur - (dif - x) = cur - dif + x$$

但 $f(u,v)$ 不能超过 $cur$，所以实际 $dist(1,n) = \min(cur,\ cur - dif + x)$。

---

六、如何计算 $dif$

$dif$ 是树中所有可能选择的 $(u,v)$ 对应的最短路径缩短量的最小值（与 $x$ 无关的部分）。

代码中通过两次 DFS 计算：

1. 第一次 DFS（calc）：

   • 计算 $d[v] = dist(0, v)$
   • 计算子树大小 siz[v]，时间戳 tin[v], tout[v]，用于判断祖先关系
   • 父节点 pr[v]

2. 第二次 DFS（dfs）：

   • 沿着 $1 \to n$ 的路径（isp(u, n-1) 判断是否在路径上）进行
   • 维护 mn = 当前路径上遇到的最大 $d[v] + w$（用于计算可能的最小缩短量）
   • 更新 dif 为所有可能的最小值

具体地：

• 如果某个不在 $1 \to n$ 路径上的子树大小 $>1$，则 dif = 0（因为可以在该子树内选两个点，使缩短量极小）
• 否则，dfs 沿着路径计算：
  • dif = min(dif, max(0, -(mn - d[v])))
  • dif = min(dif, max(0, -(d[pr[p]] - d[v])))
  • 对于不在路径上的子节点：dif = min(dif, max(0, -(mn + w - d[v])))

最终 dif 是最小可能的缩短量（与 $x$ 无关的部分）。

---

七、答案公式

对于询问的 $x$：

$$\text{ans} = \min( cur,\ cur - dif + x )$$

如果 $dif = 0$，则 $\text{ans} = \min(cur,\ cur + x) = cur$（因为 $x \ge 1$，$cur + x > cur$，所以 $\text{ans}=cur$）。

如果 $dif > 0$，则当 $x \ge dif$ 时，$\text{ans} = cur$；当 $x < dif$ 时，$\text{ans} = cur - dif + x$。

---

八、复杂度

• DFS 两次：$O(n)$
• 每个询问 $O(1)$
• 总复杂度 $O(n + m)$

---

九、代码对应公式

• $cur = d[n-1]$
• $dif$ 通过 dfs 计算
• 输出：$\min(cur,\ cur - dif + x)$

---

十、图示理解

假设 $1 \to n$ 的路径为 $P$。
添加边 $(u,v)$ 会产生一条新路径 $1 \to u \to v \to n$（或反向）。
该路径长度 $= d_u + x + d'_v$。
要让它尽量接近 $cur$，就要让 $d_u + d'_v$ 尽量接近 $cur$，即让 $u$ 和 $v$ 在 $P$ 上的投影重叠尽量少，或者让其中一端在 $P$ 外。

$dif$ 就是 $cur - \max_{u,v} \min(d_u + d'_v,\ d_v + d'_u)$ 的某种转化。

---