问题概述

Farmer John 的农场由 $N$ 个牧场和 $N-1$ 条双向道路（长度均为 $1$）构成，形成一棵树。
为了应对某条原有道路被阻断的情况，他修建了 $M$ 条额外的双向道路，每条道路有一个正整数长度（最多 $10^9$）。

任务：
对于原有的 $N-1$ 条道路中的每一条，求出如果该道路被阻断，能用来重新连接农场的最短额外道路的长度。如果没有这样的额外道路，输出 $-1$。

关键转化

将原树称为 树边，额外道路称为 非树边。

• 删除一条树边 $e$ 会把树分成两个连通块 $A$ 和 $B$。
• 一条非树边 $(x, y, w)$ 能替代 $e$，当且仅当 $x$ 和 $y$ 分别属于 $A$ 和 $B$。
• 换句话说，这条非树边 跨过 了树边 $e$。

因此：

一条非树边 $(x, y, w)$ 可以更新 树上 $x$ 到 $y$ 路径上的所有树边 的候选答案（取最小值）。

问题重构

我们初始时设每条树边的答案为 $+\infty$。

对于每条非树边 $(x, y, w)$，我们将 $x$ 到 $y$ 的路径上的所有树边的答案更新为 $\min(\text{当前答案}, w)$。

最后，每条树边的答案就是能覆盖它的非树边中的最小权值；如果仍是 $+\infty$，输出 $-1$。

算法选择

我们需要高效地实现：

操作：对树上一条路径的所有边进行取最小值操作。
查询：最后询问每条边的最终值。

这是一个典型的 树上路径更新，最后单点查询 问题。

树链剖分（HLD）思路

1. 边权转点权
   将连接 $u$（父）和 $v$（子）的树边的权值信息记录在节点 $v$ 上。
   这样，一条路径上的边权，对应路径上除 LCA 外的所有点。

2. 路径更新
   对于非树边 $(x, y, w)$：

   • 找到 $x$ 和 $y$ 的 LCA。
   • 分别更新 $x \to \text{LCA}$ 和 $y \to \text{LCA}$ 路径上的点（对应的边）的答案，与 $w$ 取最小值。
   • 使用树链剖分将路径分解为 $O(\log N)$ 条重链区间。
   • 对每个区间，在线段树上进行区间取最小值操作。

3. 线段树设计

   • 维护区间最小值（实际是“历史最小值”）。
   • 支持区间取 min（lazy 标记也是取 min）。
   • 最后对每个叶子节点（对应一条边）查询最终值。

复杂度分析

• 树链剖分预处理：$O(N)$
• 每条非树边路径更新：$O(\log^2 N)$（树链剖分 $O(\log N)$ 条区间，线段树每区间 $O(\log N)$）
• 总复杂度：$O(N + M \log^2 N)$
  对于 $N, M \le 5 \times 10^4$ 是可行的。

总结步骤

1. 读入树结构，建立邻接表，并记录每条树边对应的下方节点（用于边权转点权）。
2. 进行树链剖分预处理（dfs1 求重儿子，dfs2 剖分链）。
3. 建立线段树，初始值设为 $+\infty$。
4. 对每条非树边 $(x, y, w)$：
   • 使用 HLD 将路径 $x \to y$ 拆成区间，对每个区间在线段树上执行区间取 min。
5. 最后对每条树边，查询其对应节点的线段树值，若为 $+\infty$ 则输出 $-1$，否则输出该值。

要点回顾

• 核心是将“每条树边的最小可替代非树边”转化为“覆盖该边的所有非树边的最小权值”。
• 利用树链剖分 + 线段树实现高效的路径取 min 操作。
• 注意边权转点权的技巧，避免将 LCA 对应的边错误更新。