变形虫树 - 题目

给你一棵拥有 $N$ 个节点的树。在这棵树上，有 $M$ 只变形虫，每只变形虫占据节点的一个子集。重要的是，任何给定的变形虫所占据的节点总是形成一个连通子集。

目标是消灭所有的变形虫。这可以通过向某个节点射击来实现，射击该节点会杀死任何身体哪怕只有一部分位于该节点内的变形虫。更具体地说，如果一只变形虫分布在多个节点上，并且其中一个节点被作为目标，那么整只变形虫（无论其大小或跨越的节点数如何）都将被消灭。你需要确定消灭所有变形虫所需的最小弹药量。

图 1. 样例中的第一个测试用例。

此外，还会发生 $Q$ 个事件。在每个事件中，假设出现了一只额外的变形虫，并重新评估情况。任务是确定所需的新最小弹药量。

注意，这只新的变形虫将在事件结束时被移除（即每个事件都是独立的）。

第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。

对于每个测试用例：

第一行包含三个空格分隔的整数 $N$、$M$ 和 $Q$ ($1 \le N \le 2 \cdot 10^5$，$1 \le M \le 2 \cdot 10^5$，$0 \le Q \le 2 \cdot 10^5$)。
接下来的 $N - 1$ 行描述这棵树。每行包含两个空格分隔的整数 $x$ 和 $y$ ($1 \le x, y \le N$)，表示节点 $x$ 和节点 $y$ 之间的一条边。
接下来的 $M$ 行描述这些变形虫。每行以一个整数 $k_i$ 开始，后面跟着 $k_i$ 个空格分隔的整数 $v_{i,1}, v_{i,2}, \dots, v_{i,k_i}$ ($1 \le k_i, v_{i,j} \le N$)，其中节点 $v_{i,1}, v_{i,2}, \dots, v_{i,k_i}$ 在树中形成一个连通子集，且互不相同。
最后 $Q$ 行描述每个事件中新增的变形虫。每行以一个整数 $l_i$ 开始，后面跟着 $l_i$ 个空格分隔的整数 $u_{i,1}, u_{i,2}, \dots, u_{i,l_i}$ ($1 \le l_i, u_{i,j} \le N$)，其中节点 $u_{i,1}, u_{i,2}, \dots, u_{i,l_i}$ 在树中形成一个连通子集，且互不相同。

保证：

对于每个测试用例，输出 $Q + 1$ 行。分别表示事件发生前的答案，以及每个事件发生后的答案。请注意，第一行应包含任何事件发生之前的答案！

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

QOJ.ac