AT_kupc2021_l.Tag Game

在一棵有 $N$ 个顶点的树上，每条边的长度都是 $1$。在这棵树上将进行 $Q$ 次追逐游戏。你作为被追逐的一方，而游戏开始时，追赶你的鬼在一个与你不同的顶点上。鬼始终知道你的确切位置，并以每秒 $1$ 的速度朝你奔来。虽然你无法确定鬼的具体位置，但可以通过闻到的气味浓度得知鬼与你之间的距离。基于这些信息，你在每秒钟可以选择以下两种动作之一：

• 用 $1$ 秒时间移动到一个相邻的顶点。
• 在当前顶点停留 $1$ 秒。

如果你和鬼在某条边或某个顶点上相遇，这回合的追逐游戏就结束了。

在第 $i$ 次追逐游戏开始时，你位于顶点 $x_i$，并且鬼和你的距离是 $d_i$。你的任务是，在尽量延长与鬼相遇的时间的情况下，计算出和鬼相遇的最短时间 $s_i$。

（也就是说，问题的答案是，在不冒任何风险的情况下，依靠已知信息行动，使得与鬼相遇的最短时间最大化。假设你在边上移动是匀速的，而鬼则会按照缩短你们之间距离的方向移动。）

输入通过标准输入给出，格式如下：

$N$ $Q$ $a_1$ $b_1$ $a_2$ $b_2$ $\ldots$ $a_{N-1}$ $b_{N-1}$ $x_1$ $d_1$ $x_2$ $d_2$ $\ldots$ $x_Q$ $d_Q$

第一行包含两个整数 $N$ 和 $Q$，分别表示树的顶点数和追逐游戏的次数。接下来的 $N-1$ 行描述了树的结构，第 $i$ 行表示顶点 $a_i$ 和 $b_i$ 之间有一条边。接下去的 $Q$ 行描述每次追逐游戏的信息，第 $N+i$ 行包含两个整数 $x_i$ 和 $d_i$。

输出共 $Q$ 行，其中第 $i$ 行输出在第 $i$ 次追逐游戏中，你在尽量延长与鬼相遇的时间的情况下，与鬼相遇的最短时间 $s_i$。

约束

• $2 \leq N \leq 100,000$
• $1 \leq Q \leq 100,000$
• $1 \leq a_i, b_i \leq N$
• $1 \leq x_i, d_i \leq N$
• 对于每个 $x_i$，从其出发的距离为 $d_i$ 的顶点必然存在。
• 若 $i \neq j$，则 $(x_i, d_i) \neq (x_j, d_j)$
• 输入图一定是树。
• 所有输入均为整数。

样例解释

在第一次追逐游戏中，你从顶点 $1$ 开始，鬼和你的距离为 $4$，因此鬼在顶点 $5$。最佳策略是停留在顶点 $1$，这样 $s_1$ 就为 $4$。

在第二次追逐游戏开始时，你在顶点 $3$，而鬼和你的距离为 $1$，所以鬼可能在顶点 $2$ 或顶点 $4$。如果你朝顶点 $2$ 移动，而鬼最初在顶点 $2$，则你们将在 $0.5$ 秒后在边上相遇；如果鬼在顶点 $4$，则在 $3$ 秒后于顶点 $1$ 相遇。如此行动下，与鬼相遇的最短时间是 $0.5$ 秒。同理，若你朝顶点 $4$ 方向走，最短相遇时间也是 $0.5$ 秒。如你选择停留在顶点 $3$，无论鬼在顶点 $2$ 还是顶点 $4$，你们将都在 $1$ 秒后相遇。因此最优策略是待在顶点 $3$，此时 $s_2$ 为 $1$。

本翻译由 AI 自动生成