Problem Detail - 大工程

ID: 2155

Type: RemoteJudge

1000ms

256MiB

Difficulty: (None)

Uploaded By:

No submission language available for this problem.

题目描述

国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。

我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。

在 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

n<=1000000

q<=50000并且保证所有k之和<=2*n