国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径的长度。
现在国家有很多个计划,每个计划都是这样,我们选中了 k 个点,然后在它们两两之间 新建 (2k) 条新通道。
现在对于每个计划,我们想知道:
第一行 n 表示点数。
接下来 n−1 行,每行两个数 a,b 表示 a 和 b 之间有一条边。点从 1 开始标号。
接下来一行 q 表示计划数。对每个计划有 2 行,第一行 k 表示这个计划选中了几个点。
第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。
输出 q 行,每行三个数分别表示代价和,最小代价,最大代价。
对于 100% 的数据,1≤n≤106,1≤q≤5×104,∑k≤2×n
每个测试点的具体限制见下表:
测试点编号 | n | 特殊性质 |
---|---|---|
1∼2 | ≤104 | |
3∼5 | ≤105 | 树的形态是链 |
6∼7 | ≤105 | |
8∼10 | ≤106 |
## Description
国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。
在 $2$ 个国家 $a,b$ 之间建一条新通道需要的代价为树上 $a,b$ 的最短路径的长度。
现在国家有很多个计划,每个计划都是这样,我们选中了 $k$ 个点,然后在它们两两之间 新建 $\dbinom{k}{2}$ 条新通道。
现在对于每个计划,我们想知道:
1. 这些新通道的代价和
2. 这些新通道中代价最小的是多少
3. 这些新通道中代价最大的是多少
## Input
第一行 $n$ 表示点数。
接下来 $n-1$ 行,每行两个数 $a,b$ 表示 $a$ 和 $b$ 之间有一条边。点从 $1$ 开始标号。
接下来一行 $q$ 表示计划数。对每个计划有 $2$ 行,第一行 $k$ 表示这个计划选中了几个点。
第二行用空格隔开的 $k$ 个互不相同的数表示选了哪 $k$ 个点。
## Output
输出 $q$ 行,每行三个数分别表示代价和,最小代价,最大代价。
## Restrictions
对于 $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$ | |