CF704E Iron Man

托尼·斯塔克正在和他的战衣玩一个游戏（它们现在有自动驾驶了）。他住在马利布。马利布有 $n$ 个路口，编号从 $1$ 到 $n$，通过 $n-1$ 条道路相连。通过这些道路可以从任意一个路口到达另一个路口（马利布的路网是一棵树）。 托尼有 $m$ 套战衣。每套战衣都有一条特殊的行动计划。第 $i$ 套战衣将在时刻 $t_i$ 出现在路口 $v_i$，并以 $c_i$ 条道路每秒的速度，从 $v_i$ 沿最短路径行驶到 $u_i$（通过一个路口不耗时），到达 $u_i$ 后立即消失（如果在时刻 $q$ 到达 $u_i$，它只在时刻 $q$ 停留此处，不会在更往后的时刻出现）。同时，战衣是连续运动的（例如如果 $v_i\neq u_i$，在某个非整数时刻它可能处在某条道路的中间）。注意，如果 $v_i = u_i$，则该战衣只会在时刻 $t_i$ 在路口 $v_i$ 停留，然后立刻消失。 当任何时刻有两套战衣处于完全相同的位置（无论是在路口还是在道路上，包括出现、消失或行进过程中），就会发生爆炸。 你的任务是告诉托尼第一次爆炸发生的时刻（如果可能发生的话）。

输入的第一行包含两个整数 $n$ 和 $m$（$1\leq n,m\leq 100000$），表示路口数和战衣数。 接下来的 $n-1$ 行描述道路。每行有两个整数 $a_i$ 和 $b_i$，表示第 $i$ 条道路连接着 $a_i$ 和 $b_i$ 两个路口（$1\leq a_i,b_i\leq n,\, a_i\neq b_i$）。 接下来的 $m$ 行每行描述一套战衣。第 $i$ 行有四个整数 $t_i$、$c_i$、$v_i$、$u_i$（$0\leq t_i\leq 10000,\,1\leq c_i\leq 10000,\,1\leq v_i,u_i\leq n$），表示第 $i$ 套战衣将在时刻 $t_i$ 出现在路口 $v_i$，并以 $c_i$ 条道路每秒的速度，从 $v_i$ 移动到 $u_i$。

如果永远不会发生爆炸，输出 -1。 否则，输出第一次爆炸发生的时间。 如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，就会被认为是正确的。

由 ChatGPT 5 翻译