Public Judge

pjudge

Time Limit: 2 s Memory Limit: 1024 MB

# 21628. 【PER #1】捉迷藏

统计

有一棵 $n$ 个点的树,A 和 B 在上面捉迷藏,A 抓 B 。

初始,两个人在不同的节点。然后游戏会进行若干轮,在每一轮:

  • B 获得 A 现在到他的距离。B 每一轮都可以获取一次距离,但 B 并不知道 A 的具体位置。
  • 两人同时走一步。
    • A 总是向到 B 距离更近的方向走。
    • B 可以任意决定自己往哪走,也可以原地不动
  • 如果两人在同一个点上,或者两人穿过了同一条边,游戏结束。

B 希望最大化游戏进行的轮数。如果最后一轮是穿过了同一条边而结束的,那么这一轮视为只进行了一半。

有若干组游戏。对于第 $i$ 组游戏,会告诉你 B 的初始位置 $v_i$ 以及初始 A 到 B 的距离 $d_i$ ,你需要求出在最坏情况下 B 可以使得游戏进行几轮。

最坏情况指的是 A 总是可以处在任意一个使得之前每一轮获得的距离合法的点上,因此随机策略并没有任何作用。换句话说,“交互库是 adaptive 的”。你可以通过样例解释来更好地理解。

输入格式

第一行两个正整数 $n,Q$ ,表示点数和游戏组数。

接下来 $n-1$ 行,每行两个正整数 $u_j,v_j$ ,表示一条边。

接下来 $Q$ 行,每行两个正整数 $v_i,d_i$ ,表示一组游戏。

输出格式

输出 $Q$ 行,每行一个正整数,表示第 $i$ 组游戏的答案。可以证明答案一定是正整数。

样例 $1$

input

5 2
1 2
2 3
3 4
4 5
1 4
3 1

output

4
1

explanation

对于第一组游戏,可以直接通过距离推出 A 在 5 号点,因此 B 的最优策略是待在原地不动。

对于第二组游戏,A 可能在 2 号点也可能在 4 号点。但是无论 B 往哪边走,最坏情况都是只进行半轮就被抓到。因此最优策略仍然是待在原地不动。

样例 $2$

input

11 2
1 2
2 3
1 4
4 5
1 6
6 7
7 8
1 9
9 10
10 11
3 2
10 4

output

2
5

样例 $3\sim 6$

见下发文件。

数据范围与提示

对于所有数据,保证 $2\le n\le 10^5$,$1\le Q\le 10^5$,$1 \leq v_j \leq n$,$1 \leq d_j \leq n-1$ 。

子任务编号 追加限制 分数
$1$ $ $ $100$

时间限制:$\texttt{2s}$

空间限制:$\texttt{1024MB}$