#Pmp13. 【例题3】树上距离

【例题3】树上距离

【例题3】树上距离

题目描述

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

输入格式

第一行为两个整数n和m。

n表示点数,m表示询问次数;

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

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

输出格式

输出m行。对于每次询问,输出一行一个整数表示答案。

数据范围

(原站未提供,导入后需人工补齐)

样例

2 2 
1 2 100 
1 2 
2 1
100
100
3 2
1 2 10
3 1 15
1 2
3 2
10
25

提示

对于100%的数据,2<=n<=10^4,1<=m<=2*10^4,0<k<=100,1<=x,y<=n。