TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3989
  • 题目
  • P3989[HEOI2014 DAY1]大工程
    限制 : 时间限制 : - MS   空间限制 : 565536 KB
    问题描述

    国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。
    我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。
    在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
    现在国家有很多个计划,每个计划都是这样,我们选中了 k 个点,然后在它们两两之间
    新建 C(k,2)条
    新通道。现在对于每个计划,我们想知道:
    1.这些新通道的代价和
    2.这些新通道中代价最小的是多少
    3.这些新通道中代价最大的是多少

    输入格式

    第一行 n 表示点数。
    接下来 n-1 行,每行两个数 a,b 表示 a 和 b 之间有一条边。点从 1 开始标号。
    接下来一行 q 表示计划数。对每个计划有 2 行,第一行 k 表示这个计划选中了几个点。
    第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。

    输出格式

    输出 q 行,每行三个数分别表示代价和,最小代价,最大代价。

    样例输入

    10
    2 1
    3 2
    4 1
    5 2
    6 4
    7 5
    8 6
    9 7
    10 9
    5
    2
    5 4
    2
    10 4
    2
    5 2
    2
    6 1
    2
    6 1

    样例输出

    3 3 3
    6 6 6
    1 1 1
    2 2 2
    2 2 2

    提示

    对于第 1,2 个点:
    对于第 3,4,5 个点:
    对于第 6,7 个点:
    对于第 8,9,10 个点:
    n<=10000
    n<=100000,交通网络构成一条链
    n<=100000
    n<=1000000

    对于100%数据:q<=50000  k之和<=2*n