[APC001] F - Extend
题目背景
~~**本题输入输出量较大，请酌情使用较快的输入输出方式**~~。已扩大时限从 $1s\to 1.5s$。
题目描述
对于一棵有 $n$ 个节点，根为 $k$ 的树，最开始有且仅有一个“可扩展的”节点 $z$，我们有两种扩展形式：
- $\text{I}$ 类扩展：从一个“可扩展的”节点 $u$ 开始扩展，把 $u$ 的子树中所有节点和所有满足与 $u$ 距离 $\leq p$ 且是 $u$ 祖先的节点标记为“可扩展的”。
- $\text{II}$ 类扩展：从一个“可扩展的”节点 $u$ 开始扩展，把所有与 $u$ 深度相等的节点标记为“可扩展的”。
你需要将所有结点都标记为“可扩展的”，求最小进行扩展的次数。
输入输出格式
输入格式
第一行两个整数 $n,k$。
接下来 $n-1$ 行，每行两个整数 $u,v$，表示存在一条无向边连接 $u,v$。
接下来一行一个整数 $t$，表示询问次数。
接下来 $t$ 行，每行两个整数 $z,p$，意义如上。
输出格式
$t$ 行，对于每次询问：
- 若无法将所有节点都标记为“可扩展的”，输出 `-1`。
- 否则一行一个整数，表示答案。
输入输出样例
输入样例 #1
3 1
1 2
1 3
2
2 6
2 1输出样例 #1
2
2输入样例 #2
4 1
2 1
3 2
4 3
3
2 2
2 5
4 2输出样例 #2
1
1
2输入样例 #3
20 11
2 8
16 4
6 7
11 8
10 13
7 10
17 7
15 13
10 14
18 19
1 2
6 3
12 1
1 5
1 4
2 3
9 5
14 20
5 18
15
9 269
1 522
6 327
13 726
14 8
17 2
18 4
15 64
9 5
13 3
18 1
19 664
5 3
20 5
6 4输出样例 #3
2
2
2
2
2
3
2
2
2
3
5
2
2
3
2说明
样例 $1$ 解释：两次询问都可以先对 $2$ 节点进行 $\text{II}$ 类扩展，然后对 $3$ 进行 $\text{I}$ 类扩展。可以保证对于两次询问，这样操作都是最优的。
对于所有数据，$1\leq z,k,u,v\leq n\leq 10^5,1\leq t\leq 2\times 10^6,0\leq p\leq 10^{18}$。