P6805 [CEOI 2020] Spring Cleaning

0.3s, 128MB

Spring cleaning might be one of the most boring things in our lives. However, for Flóra and her mother, this year's spring cleaning is much more interesting, because they found a tree-shaped map covered in dust under the carpet. This tree has $N$ nodes, numbered from $1$ to $N$, connected by $N-1$ edges. Too much dust has accumulated on these edges, so Flóra's mother plans to clean the tree. The cleaning process works as follows: each time, Flóra's mother chooses two leaf nodes in the tree (a leaf node is defined as a node that is directly connected to exactly one other node), and cleans all edges on the path between these two leaves. If there are $d$ edges on the path, then the cost of this cleaning operation is $d$. When all edges in the tree have been cleaned, the cleaning process is finished. The total cost is the sum of the costs of all cleaning operations. Because she wants to protect the leaf nodes of the tree, for each leaf node, she will choose it at most once. Flóra thinks the original tree is too simple, so she decides to modify the original tree a bit. In the $i$-th modification, she adds $D_i$ leaf nodes to the original tree. Specifically, she chooses a node in the original tree and connects it to a new leaf node with an edge. Note that during the process of adding new leaf nodes, some of the original nodes will no longer be leaf nodes. Now you need to help Flóra find the minimum cost to clean the modified tree.

The first line contains two integers $N,Q$, representing the number of nodes in the original tree and the number of modifications Flóra will perform on the original tree. The next $N-1$ lines each contain two integers $u,v$, indicating that there is an edge between nodes $u$ and $v$ in the original tree. The next $Q$ lines describe the modifications. Each line starts with an integer $D_i$, meaning that Flóra will add $D_i$ leaf nodes in the $i$-th modification. Then follow $D_i$ integers; the $j$-th integer $a_j$ means that Flóra will add one leaf node attached to node $a_j$. Multiple leaf nodes may be added to the same node. Each modification is independent. That is, after finishing one modification, Flóra starts again from the original tree for the next modification.

For each modification, output one integer indicating the minimum cost to clean the modified tree. In particular, if the tree cannot be completely cleaned, output $-1$.

### Sample Explanation The following shows the tree after the second modification:  One optimal cleaning plan is to clean all edges on the three paths $1-6$, $A-7$, and $B-3$. ### Subtasks All test cases satisfy: $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$. The constraints for each subtask are as follows: | Subtask ID | Points | Constraints | | ---------- | ------ | ----------- | | $1$ | $0$ | Sample | | $2$ | $9$ | $Q=1$, for all $i \in [2,N]$, there is an edge connecting $1$ and $i$, and Flóra will not add leaf nodes to node $1$ | | $3$ | $9$ | $Q=1$, for all $i \in [1,N)$, there is an edge between $i$ and $i+1$, and Flóra will not add leaf nodes to node $1$ or node $N$ | | $4$ | $16$ | $N \leq 2 \times 10^4$, $Q \leq 300$ | | $5$ | $19$ | The original tree is a perfect binary tree rooted at node $1$, i.e., every non-leaf node has exactly two children, and the distance from each leaf to the root is the same | | $6$ | $17$ | For all $i \in [1,Q]$, $D_i=1$ | | $7$ | $30$ | No special constraints | Translated by ChatGPT 5