43481556：Dis

4348   1556：Dis

题目描述

给出 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

说明



	数据范围与提示：




	对于全部数据，2≤n≤104,1≤m≤2×104,0<k≤100,1≤x,y≤n


。
1
1
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型倍增求LCA
难        度