该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile2219.zip](file://AdditionalFile2219.zip?type=additional_file)

#2219. 「HEOI2014」大工程

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。 
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在两个国家 $a,b$ 之间建一条新通道需要的代价为树上 $a,b$ 的最短路径。

现在国家有很多个计划，每个计划都是这样，我们选中了 $k$ 个点，然后在它们两两之间 新建 $C^2_k$ 条新通道。现在对于每个计划，我们想知道：

1. 这些新通道的代价和
2. 这些新通道中代价最小的是多少
3. 这些新通道中代价最大的是多少

输入格式

第一行 $n$ 表示交通网络中的点的数量。
接下来 $n-1$ 行，每行两个数 $a,b$ 表示 $a$ 和 $b$ 之间有一条边。点从 $1$ 开始标号。
接下来一行 $q$ 表示计划数。
对每个计划有两行，第一行 $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 \leq 1000000,\ q \leq 50000$，并且保证所有 $k$ 之和不超过 $2n$。