TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1536
  • 题目
  • P1536【Usaco Oct08 Gold】奶牛串门(Pasture Walking)
    限制 : 时间限制 : 30000 MS   空间限制 : 65536 KB
    问题描述

    有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)

    输入格式

    第一行,两个用空格分隔的整数:N和Q
    第二行到第N行,第i+1行包含三个用空格分隔的整数Ai,Bi,Li
    第N+1行到第N+Q行,每行包含两个用空格分隔的整数p1,p2

    输出格式

    共Q行,每行包含每次询问的最短距离的值。

    样例输入 1

    4 2
    2 1 2
    4 3 2
    1 4 3
    1 2
    3 2

    样例输出 1

    2
    7

    样例输入 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

    样例输出 2

    8
    13
    5
    2

    提示

    样例解释:
    询问1:1->2 总代价为2
    询问2:3->4->1->2 总代价为7


    来源  Usaco October 2008 Gold