UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3611. [Heoi2014]大工程

Statistics 下载数据

Description

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

Input

第一行 n 表示点数。

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

Output

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

Sample Input

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

Sample Output

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

Hint

n<=1000000 


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

Source

鸣谢佚名上传