P11141 [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$ 解释：两次询问都可以先对 $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}$。