P11141 [APC001] F - Extend

~~**This problem has a large amount of input and output, so please use faster I/O methods when appropriate**~~. The time limit has been increased from $1s\to 1.5s$.

Given a tree with $n$ nodes and root $k$. Initially, there is one and only one “extendable” node $z$. We have two types of extensions: - Type $\text{I}$ extension: start from an “extendable” node $u$, and mark as “extendable” all nodes in the subtree of $u$, as well as all nodes that are ancestors of $u$ and satisfy that their distance to $u$ is $\leq p$. - Type $\text{II}$ extension: start from an “extendable” node $u$, and mark as “extendable” all nodes whose depth is the same as $u$. You need to mark all nodes as “extendable”. Find the minimum number of extensions needed.

The first line contains two integers $n,k$. The next $n-1$ lines each contain two integers $u,v$, indicating that there is an undirected edge between $u$ and $v$. The next line contains one integer $t$, the number of queries. The next $t$ lines each contain two integers $z,p$, with the meaning as described above.

Output $t$ lines. For each query: - If it is impossible to mark all nodes as “extendable”, output `-1`. - Otherwise, output one integer, the answer.

Explanation for Sample $1$: for both queries, you can first perform a Type $\text{II}$ extension on node $2$, and then perform a Type $\text{I}$ extension on node $3$. It can be guaranteed that for both queries, this operation is optimal. Constraints: for all testdata, $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}$. Translated by ChatGPT 5