#P3611. [Heoi2014]大工程

    ID: 2818 传统题 4000ms 512MiB 尝试: 2647 已通过: 858 难度: 8 上传者: 标签>难度分类提高+/省选-树算法虚树DFS 序排序补充相邻点 LCA栈建虚树树上倍增动态规划树形 DP组合数学贡献法模拟与实现技巧稀疏状态重置CF2400树论

[Heoi2014]大工程

[HEOI2014] 大工程

题目描述

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

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

在两个城市 a,ba,b 之间建一条新通道,代价为原树上 a,ba,b 之间的距离。

现在国家有很多个计划,每个计划都是这样,我们选中 kk 个城市,并在每一对选中城市之间新建一条通道,共新建 (k2)\dbinom{k}{2} 条通道。各计划独立计算,通道建设不影响其他计划的原树距离。

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

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

输入格式

第一行 nn 表示点数。

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

接下来一行 qq 表示计划数。对每个计划有 22 行,第一行 kk 表示这个计划选中了几个点。

第二行用空格隔开的 kk 个互不相同的数表示选了哪 kk 个点。

输出格式

输出 qq 行,每行三个数分别表示代价和,最小代价,最大代价。

当 k=0k=0 或 k=1k=1 时,不需要新建通道,三个输出值统一约定为 0 0 0。

样例 #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
3 3 3
6 6 6
1 1 1
2 2 2
2 2 2

数据范围

每个计划满足 0≤k≤n0\le k\le n,选中点互不相同。

对于 100%100\% 的数据,$1\le n\le 10^6,1\le q\le 5\times 10^4,\sum k\le 2\times n$。

每个测试点的具体限制见下表:

测试点编号 nn 特殊性质
1∼21\sim 2 ≤104\le 10^4
3∼53\sim 5 ≤105\le 10^5 树的形态是链
6∼76\sim 7
8∼108\sim 10 ≤106\le 10^6