树上的距离

题目描述

有一棵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行: 每行输出一个数，表示要查询的两点之间的简单路径上的边权和。

样例