题目描述
你有一棵 $n$ 个点的无根树，节点编号从 $1$ 开始，和一个初始为空的可重集合 $S$。有 $m$ 次向 $S$ 中加入元素的操作，第 $i$ 次操作给出原树中的 $k_i$ 条边，保证互不相同，你需要将这 $k_i$ 条边删去，得到 $k_i + 1$ 个联通块，设构成这些联通块的点的编号集合分别为 $T_{i,1}, T_{i,2}, \dots, T_{i,k_i+1}$，你需要将这些集合加入 $S$，注意每次操作是互相独立的。
在所有 $m$ 次加入操作后，有 $q$ 次询问，第 $i$ 次询问给定树上一个点 $u_i$ 和一个半径 $r_i$，对于所有原树上到 $u_i$ 简单路径边数小于等于 $r_i$ 的点的编号构成的集合 $C_i$，你需要求出 $S$ 中有多少个元素是 $C_i$ 的子集。
输入格式
第一行四个正整数 $subid, n, m, q$，其中 $subid$ 表示其符合 Subtask #id 的特殊性质，其余同题目描述。
接下来 $n-1$ 行中，第 $i$ 行两个正整数 $a_i, b_i$ 表示树上编号为 $i$ 的边的两个端点。
接下来 $m$ 行中，第 $i$ 行先输入一个正整数 $k_i$，紧接着输入 $k_i$ 个正整数表示这次操作删去的边的编号集合，保证合法且互不相同。
接下来 $q$ 行中，第 $i$ 行两个整数 $u_i, r_i$ 表示给定点的标号和半径。
输出格式
共输出 $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+\sum k,q \le$ | 特殊性质 | 分值 | 子任务依赖 |
|---|---|---|---|---|---|
| $1$ | $500$ | $500$ | 无 | $10$ | 无 |
| $2$ | $2000$ | $2000$ | 无 | $10$ | $1$ |
| $3$ | $10^5$ | $10^5$ | 第 $i$ 条边连接编号为 $i, i+1$ 的两个点 | $15$ | 无 |
| $4$ | $10^5$ | $10^5$ | $\forall i \in [1,m], k_i = 1$ | $25$ | 无 |
| $5$ | $10^5$ | $10^5$ | 无 | $35$ | $2,3,4$ |
| $6$ | $10^5$ | $3 \times 10^5$ | 无 | $5$ | $5$ |
对于所有测试点，都满足 $1 \le n \le 10^5, 1 \le m+\sum k, q \le 3 \times 10^5$，$\forall i, 0 \le r_i \le n$。