#3352. 「CEOI2020」春季大扫除

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

题目译自 CEOI 2020 Day2 T2「Spring Cleaning

春季大扫除也许是我们一生中最无聊的事情之一。当然,对于 Flóra 和她的母亲而言,今年的春季大扫除要有意思得多。因为她们在地毯下发现了一张已被灰尘覆盖的树形地图。

这棵树有 N 个节点,节点从 1 N 进行编号,这 N 个点通过 N-1 条边相连。这些边上都积累了过多的灰尘,因此 Flóra 的母亲准备对这棵树进行清理。

清理这棵树的过程是这样的:Flóra 的母亲每次在这棵树上选择两个叶子节点(定义一棵树的叶子节点为只与恰好一个点直接相连的点),并对这两个叶子点路径上的所有边进行清理。如果这条路径上有 d 条边,则清理的费用为 d 。当这棵树上的所有边都被清理后,这棵树的清理过程就完成了。清理这棵树的总费用即为各次清理的费用之和。

因为她想保护这棵树的叶子节点,因此对于每个叶子节点,她最多只会选择一次。

Flóra 认为原来的树过于简单,她决定对原始的树进行一些改造。在第 i 次改造中,她在原始的树的基础上添加了 D_i 个叶子节点。具体来说,她会在原始的树上选择一个节点,并在该点与新的叶子节点之间连接一条边。需要注意的是,在添加新的叶子节点的过程中,原来的一些节点将不再是叶子节点。

现在你需要帮助 Flóra 求出清理改造后的树的最小费用。

输入格式

输入第一行包含两个数 N,Q ,分别代表原始的树上的节点数,以及 Flóra 准备对原始的树进行的改造次数。

接下来 N-1 行,每行两个整数 u,v ,表示在原始的树上 u,v 两个节点间有一条边相连。

接下来 Q 行,每行第一个整数 D_i ,表示 Flóra 准备在第 i 次改造中添加 D_i 个叶子节点。接下来 D_i 个整数,第 j 个整数 a_j 表示 Flóra 准备在 a_j 号点上添加一个叶子节点。同一个点上可能会添加多个叶子节点。

每次改造过程是独立的,即在一轮改造后,Flóra 会在原始的树上重新开始改造过程。

输出格式

对于每次改造,你需要输出一个整数,表示清理这棵改造后的树的最小费用。

特别地,若这棵树不能被完全清理,输出 -1

样例

样例输入

7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1

样例输出

-1
10
8

样例解释

下面展示的是第二次改造后的树:

cleaning.png

一种最优的清理方案是清理 1-6 A-7 B-3 这三条路径上的所有边。

数据范围与提示

所有测试点均满足: 3 \leq N \leq 10^5 1 \leq Q \leq 10^5 \sum D_i \leq 10^5 1 \leq u,v \leq N 1 \leq a_j \leq N

各子任务的约束条件如下:

子任务编号 分值 约束
1 0 样例
2 9 Q=1 \forall i \in [2,N] ,都存在一条连接 1 i 的边,且 Flóra 不会在 1 号点上添加叶子节点
3 9 Q=1 \forall i \in [1,N) i i+1 之间有边相连,且 Flóra 不会在 1 号点或 N 号点上添加叶子节点
4 16 N \leq 2 \times 10^4 Q \leq 300
5 19 原始的树是一棵以 1 号点为根的满二叉树,即每个非叶子节点均有恰好两个子节点,且各叶子节点到根节点间的距离相等
6 17 \forall i \in [1,Q] D_i=1
7 30 无特殊约束