3332 - 树上的距离

通过次数

20

提交次数

36

时间限制 : 1 秒
内存限制 : 128 MB

有一棵n个节点的无向树,每条边有一个边权,现在有q次询问,每次询问给出两个点,求这两个点之间的简单路径上的边权和是多少。

输入

第1行两个整数n和q,n表示这棵树的节点个数,q表示查询的次数。(1<=n,q<=100000)
第2行~第n行每行有三个整数u,v,w,表示u与v之间有一条权值为w的边。(1<=w<=100000)
第n+1行~n+q行: 每行有两个正整数x,y,表示要查询的两个点的编号。

输出

第1行-第q行: 每行输出一个数,表示要查询的两点之间的简单路径上的边权和。

样例

输入

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

输出

2
7