TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1536
  • Problem
  • P1536【Usaco Oct08 Gold】奶牛串门(Pasture Walking)
    Limits : Time Limit : 30000 MS   Memory Limit : 65536 KB
    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