A91387.「HEOI2014」大工程

省选/NOI-

通过率:0%

时间限制:2.00s

内存限制:256MB

题目描述

国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。 
我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。
在两个国家 a,ba,b 之间建一条新通道需要的代价为树上 a,ba,b 的最短路径。

现在国家有很多个计划,每个计划都是这样,我们选中了 kk 个点,然后在它们两两之间 新建 Ck2C^2_k 条新通道。现在对于每个计划,我们想知道:

  1. 这些新通道的代价和
  2. 这些新通道中代价最小的是多少
  3. 这些新通道中代价最大的是多少

输入格式

第一行 nn 表示交通网络中的点的数量。
接下来 n1n-1 行,每行两个数 a,ba,b 表示 aabb 之间有一条边。点从 11 开始标号。
接下来一行 qq 表示计划数。
对每个计划有两行,第一行 kk 表示这个计划选中了几个点。
第二行用空格隔开的 kk 个互不相同的数表示选了哪 kk 个点。

输出格式

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

输入输出样例

  • 输入#1

    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

    输出#1

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

说明/提示

对于所有的数据,n1000000, q50000n \leq 1000000,\ q \leq 50000,并且保证所有 kk 之和不超过 2n2n

首页