G. D155 【LCA最近公共祖先】树上任意两点的最短距离

传统题

200ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

给出 $n$ 个点的一棵树， $n-1$ 条双向边（有边权）。有 $m$ 次询问，每次询问给出两个整数 $x \ y$ ，求点 $x$ 和点 $y$ 之间的最短距离（不需要强调谁是根节点，因为树上任意两点的最短路径是唯一的）。

第一行为两个整数 $n \ m$ （ $1 \le n \le 10^4 ,0 \le m \le 20000$ ）。

下来 $n-1$ 行，每行三个整数 $x \ y \ k$ ，表示点 $x$ 和点 $y$ 之间存在一条边长度为 $k$ （ $0 \le k \le 100$ ）。

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

输出 $m$ 行，每行一个整数，对应一次询问的答案。

100
100

10
25