[Usaco2008 Oct]牧场行走

有 $N$ 头奶牛，编号为 $1$ 到 $N$ ；同时有 $N$ 块牧场，编号也为 $1$ 到 $N$ 。第 $i$ 头奶牛正在第 $i$ 块牧场上吃草。

这些牧场由 $N-1$ 条道路连接。奶牛可以沿道路行走，其中第 $i$ 条道路连接牧场 $A_i$ 和牧场 $B_i$ ，长度为 $L_i$ 。任意两块牧场之间都可以通过这些道路互相到达，因此所有牧场和道路构成一棵树。

奶牛们经常互相拜访。请计算给定的 $Q$ 对奶牛之间的行走距离。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $Q$ ，分别表示奶牛及牧场的数量和询问数量。

接下来 $N-1$ 行，第 $i$ 行包含三个以空格分隔的整数 $A_i$ 、 $B_i$ 和 $L_i$ ，表示牧场 $A_i$ 与牧场 $B_i$ 之间有一条长度为 $L_i$ 的道路。

接下来 $Q$ 行，每行包含两个以空格分隔的整数 $P_1$ 和 $P_2$ ，表示询问第 $P_1$ 头奶牛与第 $P_2$ 头奶牛之间的距离。

对于每组询问输出一行一个整数，表示对应两头奶牛之间的距离。

2
7

本题为 USACO 2008 October 试题「牧场行走」，题面与测试数据整理自 BZOJ 1602。

2
7