3332 - 树上的距离
时间限制 : 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