← 返回题目列表

Codeforces · 1403/B

B. 春季大扫除

中文机器翻译题面 查看原题

春季大扫除可能是我们生活中最无聊的部分,除了今年,弗洛拉和她的母亲在地毯下发现了一张布满灰尘的老树图。

这棵树有 $$$N$$$ 个节点(编号从 $$$1$$$ 到 $$$N$$$),由 $$$N-1$$$ 边连接。边缘积满了太多灰尘,所以弗洛拉的妈妈决定清理它们。

清理任意树的边是通过重复以下过程来完成的:她选择 2 个不同的叶子(如果一个节点通过边恰好连接到另一个节点,则该节点是叶子),并清理它们之间最短路径上的每条边。如果该路径有 $$$d$$$ 边,则清理该路径的成本为 $$$d$$$。

她不想伤害树上的叶子,所以她最多选择每一片叶子一次。当一棵树的所有边缘都被清理干净时,它就被清理了。其成本是所有已清理路径的成本总和。

弗洛拉认为他们发现的树太小太简单,所以她想象了它的 $$$Q$$$ 变体。在第 $$$i$$$ 个变体中,她向原始树添加了总共 $$$D_i$$$ 额外叶子:对于每个新叶子,她从原始树中选择一个节点,并通过一条边将该节点与新叶子连接起来。请注意,在此步骤中某些节点可能会停止成为叶子。

对于所有这些 $$$Q$$$ 变化,我们感兴趣的是清理树所需的最低成本。

输入

第一行包含两个空格分隔的整数,$$$N$$$ 和 $$$Q$$$ ($$$3 \leq N \leq 10^{5}$$$, $$$1 \leq Q \leq 10^{5}$$$) – 树的节点数和变体数。

接下来的 $$$N-1$$$ 行包含两个空格分隔的整数 $$$u$$$ 和 $$$v$$$ 表示节点 $$$u$$$ 和 $$$v$$$ 通过边连接 ($$$1 \leq u, v \leq N$$$)。

接下来的 $$$Q$$$ 行描述了这些变化。 第 $$$i$$$ 行中的第一个整数是 $$$D_i$$$ ($$$1 \leq D_i \leq 10^{5}$$$)。然后$$$D_i$$$后面是空格分隔的整数:如果第$$$j$$$个数字是$$$a_j$$$,则意味着Flóra向节点$$$a_j$$$添加了一个新叶子($$$1 \leq a_j \leq N$$$)。我们可以向同一节点添加多个叶子。 $$$\sum_{1}^{Q} D_i \leq 10^{5}$$$ 即所有变体中 $$$D_i$$$ 的总和至多为 $$$10^5$$$。

每次变化后,Flóra 都会重新启动并向原始树添加额外的叶子。

输出

您应该打印 $$$Q$$$ 行。在第 $$$i$$$ 行中,打印一个整数:清理树的第 $$$i$$$ 变体所需的最小成本。如果树无法清理,请打印 $$$-1$$$。

示例

输入 #1

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

输出 #1

-1
10
8

注意

评分:
$$$ \begin{array}{|c|c|l|} \hline \text{子任务} & \text{点} & \text{约束} \\ \hline 1 & 0 & \text{样本}\\ \hline 2 & 9 & Q = 1, \text{节点之间有一条边} \: 1 \: \text{和} \: i \: \text{for every} \: i \: (2 \leq i \leq N), \\ & & \text{Flóra 无法向节点添加额外的叶子} \: 1 \\ \hline 3 & 9 & Q = 1, \text{节点之间有一条边} \: i \: \text{和} \: i+1 \: \text{for all} \: (1 \leq i < N), \\ & & \text{Flóra 不能添加额外的叶子到节点} \: 1 \: \text{nor 节点} \: N \\ \hline 4 & 16 & N \leq 20000, Q \leq 300\\ \hline 5 & 19 & \text{原始树是以节点 $$$1$$$为根的完美二叉树} \\ & & \text{(即每个内部节点都有 $$$2$$$ 子节点,并且每个叶子} \\ & & \text{与根的距离相同)}\\ \hline 6 & 17 & D_i = 1 \: \text{对于所有} \: i\\ \hline 7 & 30 & \text{没有附加约束}\\ \hline \end{数组} $$$

下图显示了第二种变化。 一个可能的解决方案是清理叶子 $$$1 - 6$$$、$$$A - 7$$$ 和 $$$ B - 3$$$ 之间的路径。

您可以在此处下载上述示例和附加(更大)示例输入:https://gofile.io/d/8QlbsS