A91387.「HEOI2014」大工程
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:256MB
题目描述
国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。
在两个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划,每个计划都是这样,我们选中了 k 个点,然后在它们两两之间 新建 Ck2 条新通道。现在对于每个计划,我们想知道:
- 这些新通道的代价和
- 这些新通道中代价最小的是多少
- 这些新通道中代价最大的是多少
输入格式
第一行 n 表示交通网络中的点的数量。
接下来 n−1 行,每行两个数 a,b 表示 a 和 b 之间有一条边。点从 1 开始标号。
接下来一行 q 表示计划数。
对每个计划有两行,第一行 k 表示这个计划选中了几个点。
第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。
输出格式
输出 q 行,每行三个数分别表示代价和,最小代价,最大代价。
输入输出样例
输入#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
说明/提示
对于所有的数据,n≤1000000, q≤50000,并且保证所有 k 之和不超过 2n。