← 返回题目列表

Codeforces · 758/E

E. 断树

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

给定一棵树,它有 n 个顶点,编号从 1 到 n,其中第 1 号顶点是根。每条边都有权重 wi 和强度 pi。

植物学家 Innokentiy 是信息学奥林匹克竞赛评委团的唯一成员,他不喜欢折断的树木。

如果存在这样一条边,该边的强度小于它所通向的子树边的权重之和,则树被破坏。

允许将任何边的权重减少任意整数值,但随后其边的强度会减少相同的值。这意味着如果边的权重为 10,强度为 12,则权重减少 7,其权重将等于 3,强度将等于 5。

不允许增加边的重量。

你的任务是通过减少给定树的边的权重来获得不被破坏的树,并且所有边都应该具有正权重,而且所有边的总权重应该尽可能大。

显然,边的强度不能为负,但是如果子树的权重为零,则边的强度可以为零。

输入

第一行包含整数 n (1 ≤ n ≤ 2·105) — 树中的顶点数。接下来的 n - 1 行包含边的描述。每行包含四个整数 x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109),其中 x 和 y — 连接边的顶点(顶点号 x 是顶点号 y 的父节点),w 和 p 分别是边的权重和强度。保证边描述的是根在顶点 1 的树。

输出

如果不可能从给定的树中获得完整的树,则在唯一的行中打印-1。

否则,输出数据应包含 n 行:

在第一行中打印数字 n — 树上的顶点数。

在接下来的 n - 1 行中打印生成的树的边的描述。每行应包含四个整数 x、y、w、p(1 ≤ x、y ≤ n、1 ≤ w ≤ 109、0 ≤ p ≤ 109),其中 x 和 y — 边连接的顶点(顶点编号 x 是顶点编号 y 的父级),w 和 p 分别是新的权重和边的强度。

按照输入数据中给出的顺序打印边缘:不应更改每行的前两个整数。

示例

输入 #1

3
1 3 5 7
3 2 4 3

输出 #1

3
1 3 5 7
3 2 4 3

输入 #2

4
1 3 2 3
3 4 5 1
3 2 3 3

输出 #2

-1

输入 #3

5
1 2 2 4
2 4 1 9
4 5 5 6
4 3 4 8

输出 #3

5
1 2 2 4
2 4 1 9
4 5 1 2
4 3 2 6

输入#4

7
1 2 5 2
2 3 4 3
1 4 3 7
4 5 4 1
4 6 3 2
6 7 1 6

输出#4

7
1 2 5 2
2 3 2 1
1 4 3 7
4 5 3 0
4 6 3 2
6 7 1 6