题目描述

给出 $n$ 个点的一棵树，多次询问两点之间的最短距离。

注意：边是双向的。

---

输入格式

第一行为两个整数 $n$ 和 $m$。$n$ 表示点数，$m$ 表示询问次数；

接下来 $n-1$ 行，每行三个整数 $x, y, k$，表示点 $x$ 和点 $y$ 之间存在一条边长度为 $k$；

再接下来 $m$ 行，每行两个整数 $x, y$，表示询问点 $x$ 到点 $y$ 的最短距离。

---

输出格式

输出 $m$ 行。对于每次询问，输出一行结果。

---

样例

输入样例 1

2 2 
1 2 100 
1 2 
2 1

输出样例 1

100
100

样例解释 1

树只有一条边，连接 $1$ 和 $2$，长度为 $100$，所以任意询问两点距离都是 $100$。

---

输入样例 2

3 2
1 2 10
3 1 15
1 2
3 2

输出样例 2

10
25

样例解释 2

树的结构：

    1
   / \
 10   15
 /     \
2       3

• 询问 $1$ 到 $2$：距离 $10$。
• 询问 $3$ 到 $2$：路径 $3 \to 1 \to 2$，距离 $15 + 10 = 25$。

---

数据范围

• $2 \le n \le 10^4$
• $1 \le m \le 2 \times 10^4$
• $0 < k \le 100$
• $1 \le x, y \le n$

时间限制：1000 ms
内存限制：524288 KB

---

提示

这是一个标准的树上两点距离查询问题。

对于树上任意两点 $u, v$，设它们的最近公共祖先为 $lca(u, v)$，则距离公式为：

$$dist(u, v) = depth[u] + depth[v] - 2 \times depth[lca(u, v)]$$

其中 $depth[x]$ 表示节点 $x$ 到根节点的距离（即路径上所有边权之和），而不是深度（边数）。

另一种更直接的方法：预处理每个节点到根节点的距离 $dis[i]$，那么：

$$dist(u, v) = dis[u] + dis[v] - 2 \times dis[lca(u, v)]$$

这个公式成立是因为 $dis[u]$ 和 $dis[v]$ 都包含从根到 $lca$ 的路径，减去两倍的 $dis[lca]$ 就得到 $u$ 到 $v$ 的路径长度。

实现步骤：

1. 任选一个节点作为根（比如节点 $1$），DFS 预处理：
   • 每个节点的深度（用于 LCA 跳跃）；
   • 每个节点到根的距离 $dis[i]$；
   • 倍增数组 $fa[u][k]$ 表示 $u$ 的 $2^k$ 级祖先。
2. 对于每个询问 $(u, v)$：
   • 用倍增法求出 $lca(u, v)$；
   • 输出 $dis[u] + dis[v] - 2 \times dis[lca]$。

时间复杂度：预处理 $O(n \log n)$，每次询问 $O(\log n)$，总复杂度 $O(n \log n + m \log n)$，对于 $n \le 10^4, m \le 2 \times 10^4$ 完全足够。

也可以使用 Tarjan 离线算法 $O(n+m)$，但倍增法更易于实现。