题目描述
给出
n
n 个点的一棵树，多次询问两点之间的最短距离。
注意：边是双向的。
输入
第一行为两个整数
n
n 和
m
m。
n
n 表示点数，
m
m 表示询问次数；
下来
n-1
n−1 行，每行三个整数
x ,y, k
x,y,k，表示点
x
x 和点
y
y 之间存在一条边长度为
k
k；
再接下来
m
m 行，每行两个整数
x, y
x,y，表示询问点
x
x 到点
y
y 的最短距离。
输出
输出
m
m 行。对于每次询问，输出一行。
样例输入
【样例输入1】
2 2
1 2 100
1 2
2 1
【样例输入2】
3 2
1 2 10
3 1 15
1 2
3 2
样例输出
【样例输出1】
100
100
【样例输出2】
10
25
提示
数据范围与提示
对于全部数据，
2\le n\le 10^4,1\le m\le 2\times 10^4,0\lt k\le 100,1\le x,y\le n
2≤n≤104,1≤m≤2×104,0
来源/分类
ybttg LCA