配点 : 500 点
問題文
N 我有一棵顶点树。这棵树所有边的长度都是 1 。在这棵树上 Q 我们来玩捉人游戏吧。你是那个逃跑的人,而恶魔在双打游戏开始时与你处于不同的巅峰。恶魔总是知道你在哪里,每一秒都知道 它会以 1 的速度追你。你不知道恶魔的位置,但总能从恶魔气味的浓度判断出它的距离。根据该信息, 2 两个动作中 1 做一件事。
- 1 以秒为单位前进到相邻顶点
- 1 在当前顶点停留几秒
如果你在边缘或顶点遇到恶魔,那么这场捉人游戏就结束了。
i 在捉人游戏的第三局开始时,你处于顶部。 x_i 到恶魔的距离是 我们知道 d_i 。遇到恶魔的最短时间 行动时最大化遇见恶魔的最短时间 s_i 。
(换句话说,答案是根据你获得的信息,在不下注的情况下移动时,遇到恶魔所需的最短时间。而且,边缘上的移动是匀速运动,恶魔会向与你距离缩短的方向移动。) 与
制約
- 2 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 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)
- 给定的图始终是一棵树。
- 所有输入均为整数。
入力
输入将以以下形式从标准输入给出。
N Q
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}
x_1 d_1
x_2 d_2
\vdots
x_Q d_Q
1 该行的顶点数 N 和标签游戏数量 输入 Q 。2 在 N 给出了有关树的行信息。i+1 顶点在行中 它表明 a_i,b_i 通过边连接。 N+1 在 N+Q 在线 Q 给出了有关捉人游戏的信息。N+i 在线 i 第一局标签游戏开始时您所在的顶部 x_i 以及当时与恶魔的距离 上线 d_i 被给予。
出力
s_1 s_2 \vdots s_Q
i 在行中 i 在标签的第一局游戏中,最大化遇到恶魔之前的时间最小值时,遇到恶魔之前的时间最小值 可以证明 s_i 。s_i 始终是整数。
入力例1
5 2 1 2 2 3 3 4 4 5 1 4 3 1
出力例1
4 1
1 在标签的第三场比赛开始时,您将位于顶部。 1 到恶魔的距离是 4也就是说,恶魔在顶端 我在 5 。在这种情况下,顶点 1 中的行为是最佳的,s_1 = 4 。
2 在标签的第三场比赛开始时,您将位于顶部。 3 到恶魔的距离是 1也就是说,恶魔在顶端 我在 2 或顶点 您位于 4 。在此之后您将处于顶部 如果它朝 2 方向移动,恶魔将从顶部开始。 当我在 2 时0.5 几秒钟后,它们在边缘和顶点处相遇 4 时3 秒后的顶点 我们在 1 见面。因此,当你采取这个行动时,遇到恶魔所需的最短时间是 0.5 。 顶点 同样,当向 4 方向移动时,直到遇到恶魔的最小值为 0.5 。 如果你不动的话,上面 如果它停留在 3 ,则恶魔将位于顶部。 当我在 2 时 1 秒后,顶点 即使我在 4 我们将在 1 秒后见面。因此,当你采取这个行动时,遇到恶魔所需的最短时间是 1 。
因此,您的最佳行为是 通过停留在 3 ,到那时你遇到恶魔的最短时间 s_2 是 它仅由 1 。
入力例2
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
出力例2
2 5