P14622 [2019 KAIST RUN Fall] Wind of Change

本题的原标题是“无一点树乘积度量 Voronoi 图查询”。 给定两个大小为 $N$ 的带权树 $T_1$ 和 $T_2$，其中每个顶点用数字 $1 \ldots N$ 标记。设 $dist(T_1,\ i,\ j)$ 为树 $T_1$ 中从节点 $i$ 到节点 $j$ 的最短路径的总权重，类似地定义 $dist(T_2,\ i,\ j)$。 考虑一个大小为 $N$ 的点集。类似于曼哈顿度量（实际上，这是它的推广），我们可以定义两个点 $1 \le i,\ j \le N$ 之间的距离：它是两个距离之和，即 $dist(T_1,\ i,\ j) + dist(T_2,\ i,\ j)$。对于每个 $1 \le i \le N$，请确定从点 $i$ 出发的"最近点"。形式化地说，对于每个 $i$，你需要找到 $\min_{j \neq i}{dist(T_1,\ i,\ j) + dist(T_2,\ i,\ j)}$。

第一行给出一个整数 $N$，表示两棵树中的顶点数（$2 \le N \le 250,000$）。 接下来的 $N-1$ 行给出第一棵树的描述。这 $N-1$ 行中的每一行包含三个整数 $S_i, E_i, W_i$，表示存在一条连接顶点 $S_i$ 和 $E_i$ 且权重为 $W_i$ 的边（$1 \le S_i, E_i \le N$，$1 \le W_i \le 10^9$）。 接下来的 $N-1$ 行以相同格式给出第二棵树的描述。

输出 $N$ 行，每行包含一个整数。在第 $i$ 行，你应输出一个整数表示点 $i$ 的答案。

翻译由 DeepSeek V3 完成