#P18059. Amoeba Tree
Amoeba Tree
Amoeba Tree
给定一棵有 个顶点的树,树上有 只变形虫。每只变形虫占据树上的一个非空顶点集合,保证该集合在树上连通。
你可以向任意顶点射击一次,消耗一发子弹。只要某只变形虫占据的集合包含被射击的顶点,它就会被整只消灭。求消灭所有变形虫所需的最少子弹数。
此外还有 次询问,每次给出一只额外出现的变形虫,询问此时消灭所有变形虫所需的最少子弹数。所有询问相互独立:每次只在最初的 只变形虫基础上加入当前这一只,不保留之前询问加入的变形虫,也不保留射击效果。
输入格式
第一行一个整数 ,表示测试用例数。
每组数据包含:
- 第一行三个整数 。
- 接下来 行,每行两个整数 ,表示一条树边。
- 接下来 行,第 行先给出 ,再给出 个顶点,表示第 只变形虫占据的集合。
- 接下来 行,第 行先给出 ,再给出 个顶点,表示第 次询问额外加入的变形虫。
每个集合内部的顶点两两不同,并且诱导出连通子图。不同变形虫的集合可以相同。
输出格式
每组数据输出 行:第一行为没有额外变形虫时的答案,之后依次输出每次询问的答案。
数据范围
,,,,顶点编号为 到 。
跨所有测试用例,以下五个总和各自不超过 :、、、所有 的总和、所有 的总和。
样例
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