← 返回题目列表

Codeforces · 704/E

E. 钢铁侠

中文机器翻译题面 查看原题

托尼·斯塔克正在用他的套装玩游戏(它们现在有自动驾驶仪)。他住在马里布。马里布有n个路口,编号从1到n,与n-1条道路相连。人们可以使用这些道路从一个路口到达任何其他路口(马里布的图形形成一棵树)。

托尼有m套套装。每套西装都有一个特殊的计划。第 i 个衣服将在时间 ti 出现在交汇点 vi 中,并使用 vi 和 ui 之间的最短路径以每秒 ci 路的速度移动到交汇点 ui(通过交汇点不需要时间),并在到达 ui 时立即消失(如果在时间 q 到达 ui,则在 q 时刻可用,但在以后的时刻不再可用)。另外,花色会连续移动(例如,如果 vi ≠ ui,则在时间 $${ t _ { i } + \frac { 1 } { 2 c _ { i } } }$$ 时,花色位于路中间。请注意,如果 vi = ui,则意味着花色仅在时刻 ti 位于交汇处 vi 处,然后消失。

如果在任何时刻两套套装共享相同的确切位置(可能在路口或道路上的某个地方;出现、消失或移动时),就会发生爆炸。

你的任务是告诉托尼第一次爆炸的时刻(如果有的话)。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100 000)——分别是连接点的数量和花色的数量。

接下来的 n - 1 行包含道路描述。每行包含两个整数 ai 和 bi - 第 i 条路的端点(1 ≤ ai,bi ≤ n,ai ≠ bi)。

接下来的 m 行包含套装描述。其中第 i 个包含四个整数 ti、ci、vi 和 ui(0 ≤ ti ≤ 10 000、1 ≤ ci ≤ 10 000、1 ≤ vi、ui ≤ n),这意味着第 i 个花色将在 ti 时刻出现在交叉点 vi 处,并以每秒 ci 条路的速度移动到交叉点 ui。

输出

如果根本不会发生爆炸,请在输出的第一行也是唯一一行中打印 -1。

否则打印第一次爆炸的时刻。

如果您的答案的相对或绝对误差不超过 10 - 6,则视为正确。

示例

输入 #1

6 4
2 5
6 5
3 6
4 6
4 1
27 6 1 3
9 5 1 6
27 4 3 4
11 29 2 6

输出 #1

27.3

输入 #2

6 4
3 1
4 5
6 4
6 1
2 6
16 4 4 5
13 20 6 2
3 16 4 5
28 5 3 5

输出 #2

-1