9580 - 大工程

通过次数

0

提交次数

0

时间限制 : 4 秒
内存限制 : 512 MB

国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。

我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。

2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径的长度。

现在国家有很多个计划,每个计划都是这样,我们选中了 k 个点,然后在它们两两之间 新建 \dbinom{k}{2} 条新通道(任意两点间都新建 1 条)。

现在对于每个计划,我们想知道:

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

输入

第一行 n 表示点数。

接下来 n-1 行,每行两个数 a,b 表示 ab 之间有一条边。点从 1 开始标号。

接下来一行 q 表示计划数。对每个计划有 2 行,第一行 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

提示

对于 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

来源

河北省选