7611: BZOJ3611：[Heoi2014]大工程

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

输入格式

第一行 n 表示点数。

输出格式

输出 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 

题目来源

鸣谢佚名上传