#PQJ1854x9632. QOJ 1854_9632

    ID: 2727 传统题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测并查集树上算法

QOJ 1854_9632

标题: 联通块 - Problem - QOJ.ac

#9632. 联通块

Statistics

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。