中文
日本語
English
| P1536【Usaco Oct08 Gold】奶牛串门(Pasture Walking) | |
|
Description
有N (2 <= N <= 1,000)头奶牛，分别编号为1到N。还有N颗牧草分别编号为1到N。简单起见，第i头奶牛都盯着第i颗牧草。
有几对牧草分别用一些小路连接了起来，总共有N-1条双向的小路，小路i连接了Ai及Bi颗牧草(1 <= Ai <= N; 1 <= Bi <= N)，小路的长度为Li (1 <= Li <= 10,000)保证任意两颗牧草总能通过小路走到，也就是说这些小路构成了一棵树。
奶牛是群居性的动物，很喜欢串门。奶牛们会问你Q次问题(1 <= Q <= 1,000)，每次询问的内容很简单，就是从p1颗牧草到p2颗牧草最短的距离是多少。(1 <= p1 <= N; 1 <=p2 <= N)
Input Format
第一行，两个用空格分隔的整数：N和Q
第二行到第N行，第i+1行包含三个用空格分隔的整数Ai,Bi,Li
第N+1行到第N+Q行，每行包含两个用空格分隔的整数p1,p2
Output Format
共Q行，每行包含每次询问的最短距离的值。
Sample Input 1
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
Sample Output 1
2
7
Sample Input 2
8 4
6 4 5
1 4 3
7 5 5
5 2 3
3 6 4
2 6 2
8 6 8
1 6
8 5
6 4
6 2
Sample Output 2
8
13
5
2
Hint
样例解释：
询问1：1->2 总代价为2
询问2：3->4->1->2 总代价为7
Source Usaco October 2008 Gold