#P18059. Amoeba Tree

Amoeba Tree

Amoeba Tree

给定一棵有 NN 个顶点的树,树上有 MM 只变形虫。每只变形虫占据树上的一个非空顶点集合,保证该集合在树上连通。

你可以向任意顶点射击一次,消耗一发子弹。只要某只变形虫占据的集合包含被射击的顶点,它就会被整只消灭。求消灭所有变形虫所需的最少子弹数。

此外还有 QQ 次询问,每次给出一只额外出现的变形虫,询问此时消灭所有变形虫所需的最少子弹数。所有询问相互独立:每次只在最初的 MM 只变形虫基础上加入当前这一只,不保留之前询问加入的变形虫,也不保留射击效果。

输入格式

第一行一个整数 TT,表示测试用例数。

每组数据包含:

  • 第一行三个整数 N,M,QN,M,Q。
  • 接下来 N−1N-1 行,每行两个整数 x,yx,y,表示一条树边。
  • 接下来 MM 行,第 ii 行先给出 kik_i,再给出 kik_i 个顶点,表示第 ii 只变形虫占据的集合。
  • 接下来 QQ 行,第 ii 行先给出 lil_i,再给出 lil_i 个顶点,表示第 ii 次询问额外加入的变形虫。

每个集合内部的顶点两两不同,并且诱导出连通子图。不同变形虫的集合可以相同。

输出格式

每组数据输出 Q+1Q+1 行:第一行为没有额外变形虫时的答案,之后依次输出每次询问的答案。

数据范围

1≤T≤1031\le T\le10^3,1≤N,M≤2⋅1051\le N,M\le2\cdot10^5,0≤Q≤2⋅1050\le Q\le2\cdot10^5,1≤ki,li≤N1\le k_i,l_i\le N,顶点编号为 11 到 NN。

跨所有测试用例,以下五个总和各自不超过 2⋅1052\cdot10^5:∑N\sum N、∑M\sum M、∑Q\sum Q、所有 kik_i 的总和、所有 lil_i 的总和。

样例

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
2
3
2
2
1