#1874. 联通块
联通块
联通块
题目描述
标题: 联通块 - Problem - QOJ.ac
#9632. 联通块
The problem was used in the following contests:
题目描述
你有一棵 n 个点的无根树,节点编号从 1 开始,和一个初始为空的可重集合 S。有 m 次向 S 中加入元素的操作,第 i 次操作给出原树中的 ki 条边,保证互不相同,你需要将这 ki 条边删去,得到 ki+1 个联通块,设构成这些联通块的点的编号集合分别为 Ti,1,Ti,2,…,Ti,ki+1,你需要将这些集合加入 S,注意每次操作是互相独立的。
在所有 m 次加入操作后,有 q 次询问,第 i 次询问给定树上一个点 ui 和一个半径 ri,对于所有原树上到 ui 简单路径边数小于等于 ri 的点的编号构成的集合 Ci,你需要求出 S 中有多少个元素是 Ci 的子集。
输入格式
第一行四个正整数 subid,n,m,q,其中 subid 表示其符合 Subtask #id 的特殊性质,其余同题目描述。
接下来 n−1 行中,第 i 行两个正整数 ai,bi 表示树上编号为 i 的边的两个端点。
接下来 m 行中,第 i 行先输入一个正整数 ki,紧接着输入 ki 个正整数表示这次操作删去的边的编号集合,保证合法且互不相同。
接下来 q 行中,第 i 行两个整数 ui,ri 表示给定点的标号和半径。
输出格式
共输出 q 行,第 i 行表示第 i 个询问的答案。
样例输入 1
1 7 1 3
1 3
1 2
1 4
7 2
5 4
2 6
2 4 5
4 3
7 3
2 1
样例输出 1
3
2
1
样例输入 2
1 15 3 5
12 7
5 13
1 5
1 6
15 1
4 11
1 3
4 8
1 2
1 7
3 4
13 14
10 6
9 4
2 1 10
2 6 12
2 3 12
4 2
1 0
15 3
8 5
6 5
样例输出 2
1
0
3
6
9
数据范围
Subtask n m+∑k,q≤ 特殊性质 分值 子任务依赖 1 500 500 无 10 无 2 2000 2000 无 10 1 3 105 105 第 i 条边连接编号为 i,i+1 的两个点 15 无 4 105 105 ∀i∈[1,m],ki=1 25 无 5 105 105 无 35 2,3,4 6 105 3×105 无 5 5
对于所有测试点,都满足 1≤n≤105,1≤m+∑k,q≤3×105,∀i,0≤ri≤n。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1 7 1 3
1 3
1 2
1 4
7 2
5 4
2 6
2 4 5
4 3
7 3
2 1
3
2
1
样例 2
1 15 3 5
12 7
5 13
1 5
1 6
15 1
4 11
1 3
4 8
1 2
1 7
3 4
13 14
10 6
9 4
2 1 10
2 6 12
2 3 12
4 2
1 0
15 3
8 5
6 5
1
0
3
6
9