← 返回题目列表

Codeforces · 1188/A2

A2. 在树上添加:革命

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

请注意,这是两个类似问题中的第二个问题。如果你解决了这个问题,你就可以破解它。但只有解决了这两个问题,才能破解前一个问题。

给你一棵有 $$$n$$$ 个节点的树。一开始,$$$0$$$ 写在所有边上。在一项操作中,您可以选择任何 $$$2$$$ 不同叶子 $$$u$$$、$$$v$$$ 和任何整数 $$$x$$$,并将 $$$x$$$ 添加到 $$$u$$$ 和 $$$v$$$ 之间简单路径上所有边上写入的值。请注意,在之前的子任务中 $$$x$$$ 允许为任何实数,这里它必须是整数。

例如,在下图中,您可以看到对图形应用两个操作的结果:在从 $$$7$$$ 到 $$$6$$$ 的路径上添加 $$$2$$$,然后在从 $$$4$$$ 到 $$$5$$$ 的路径上添加 $$$-1$$$。

给你一些非负整数成对不同偶数的配置,写在边缘上。对于给定的配置,确定是否可以通过这些操作来实现它,如果可能,则输出导致给定配置的操作序列。操作的约束列在输出格式部分。

叶子是$$$1$$$ 度树的一个节点。简单路径是不包含任何节点两次的路径。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$) — 树中的节点数。

接下来的 $$$n-1$$$ 行包含三个整数 $$$u$$$, $$$v$$$, $$$val$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$, $$$0 \le val \le 10\,000$$$),意味着节点之间有一条边$$$u$$$ 和 $$$v$$$ 上面写有 $$$val$$$。保证这些边形成一棵树。保证所有 $$$val$$$ 数字成对不同且偶数。

输出

如果没有任何操作序列导致给定的配置,则输出“NO”。

如果存在,则在第一行输出“YES”。在第二行中,输出 $$$m$$$ — 您要应用的操作数 ($$$0 \le m \le 10^5$$$)。请注意,您不必最小化操作数量!

在接下来的 $$$m$$$ 行中,按以下格式输出操作:

$$$u, v, x$$$ ($$$1 \le u, v \le n$$$, $$$u \not = v$$$, $$$x$$$ — 整数,$$$-10^9 \le x \le 10^9$$$),其中 $$$u, v$$$ — 叶子,$$$x$$$ — 我们要添加的数字。

保证如果存在产生给定配置的操作序列,则存在满足上述所有条件的产生给定配置的操作序列。

示例

输入 #1

5
1 2 2
2 3 4
3 4 10
3 5 18

输出 #1

NO

输入 #2

6
1 2 6
1 3 8
1 4 12
2 5 2
2 6 4

输出 #2

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

注意

第一个示例的配置如下所示,这是不可能实现的。

第二个示例的操作顺序如下所示。