P4103 [HEOI2014] 大工程

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

无

无

对于 $100\%$ 的数据，$1\le n\le 10^6,1\le q\le 5\times 10^4,\sum k\le 2\times n$。 每个测试点的具体限制见下表： | 测试点编号 | $n$ | 特殊性质 | | :-----------: | :-----------: | :-----------: | | $1\sim 2$ | $\le 10^4$ | | |$3\sim 5$ | $\le 10^5$ | 树的形态是链 | | $6\sim 7$ | $\le 10^5$ | | | $8\sim 10$ | $\le 10^6$ | |