← 返回题目列表

Codeforces · 822/F

F. 疯狂

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

第二学期在巴甫洛波利斯大学开始。在维克波利斯度假后,努拉需要返回巴甫洛波利斯并继续她的学习。

有时(或经常)有些老师不喜欢你。顺便说一句,Noora 也有一位这样的老师。他的名字叫尤里·德米特里耶维奇(Yury Dmitrievich),教授图论。尤里·德米特里耶维奇不喜欢努拉,所以他总是给这个女孩布置最困难的任务。所以这次就出事了。

老师给了 Noora 一棵有 n 个顶点的树。顶点用 1 到 n 之间的整数进行编号。这棵树所有边的长度都是 1。Noora 选择一组成对在边上不相交的简单路径。然而,每个顶点应至少属于所选路径之一。

对于每个选定的路径,执行以下操作:

1. 我们选择属于该路径的一条边 (u, v)。
2. 在选定的边 (u, v) 上,有一个点位于距顶点 u 的选定距离 x 处,距顶点 v 的距离 1 - x 处。但是 Noora 任意选择距离 x,i。 e.对于不同的边缘它可以是不同的。
3. 选择顶点 u 或 v 之一。该点将开始移动到选定的顶点。

让我们通过例子解释一下点是如何移动的。假设路径由两条边 (v1, v2) 和 (v2, v3) 组成,该点最初位于边 (v1, v2) 上并开始移动到顶点 v1。然后该点将到达v1,然后“掉头”,因为到达了路径的终点,进一步它将向另一个方向移动到顶点v2,然后到顶点v3,然后再次“掉头”,然后移动到v2,依此类推。点的速度为每秒 1 个边缘。例如,在 0.5 秒内,点移动到边缘一半的长度。

在树的每个顶点放置一个秒表。开始时秒表指示的时间为 0 秒。然后在开始时刻,所有点同时开始沿着选定路径从选定位置向选定方向移动,并且秒表同时启动。当其中一点到达顶点 v 时,顶点 v 处的秒表自动重置,即从零开始计时。

resv 表示如果点运动无限继续,顶点 v 处的秒表将显示的最长时间。 Noora 被要求选择路径和路径上的点,以使 res1 尽可能小。如果有多种解决方案可以做到这一点,则需要最小化res2,然后是res3,res4,...,resn。

帮助Noora完成老师的任务。

为了更好地理解该语句,请参阅示例的解释。

输入

第一行包含单个整数 n (2 ≤ n ≤ 100) — 给定树中的顶点数。

接下来的 n - 1 行中的每一行都包含两个整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v) — 由边连接的顶点。

保证输入定义有效的树。

输出

在第一行打印单个整数路径 - 您要选择的路径数。

在接下来的路径行中打印路径的描述:

1. 单个整数 len — 当前路径中的边数。
2. len 整数 — 路径中边的索引。边按照输入中给出的顺序从 1 到 n - 1 进行编号。
3. 两个整数 u 和 v — 意味着您将点放在顶点 u 和 v 之间的边缘上(显然该边缘应该属于路径),并且一个点将开始移动到顶点 v。请注意,边缘末端的打印顺序很重要。例如,如果您打印“1 2”(不带引号),则点将开始移动到顶点 2;但如果你打印“2 1”(不带引号),那么点将开始移动到顶点 1。
4. 单个实数 x (0 ≤ x ≤ 1) — 点与顶点 u(与第三段中第一个打印的顶点相同)之间的距离。

示例

输入 #1

3
1 2
2 3

输出 #1

2
1 1 1 2 0.6666666666
1 2 2 3 0.6666666666

注意

评分:
裁判系统将使用参赛者提供的输出数据生成数组资源。此外,系统将根据陪审团的回答生成数组 resOptimal。如果仅对于每个 i (1 ≤ i ≤ n) 满足以下条件,您的答案将被接受:$$\frac{|res_i - resOptimal_i|}{max(1, resOptimal_i)} \leq 10^{-6}$$。

考虑一个例子。

在开始时刻时间点的位置如下:

第一条路径以红色突出显示,第二条路径以蓝色突出显示,绿色圆圈代表所选点,顶点内的棕色数字 - 秒表的当前时间。紫色箭头表示点移动的方向。

在 0.(3) 秒内,点将按以下方式定位(在秒表重置之前):

秒表重置后:

移动开始后 1.0 秒内:

开始移动后 1.(3) 秒内(秒表重置后):

最后,在开始移动后的2秒内点返回到其初始位置。

这个过程将无限地持续下去。