请注意,这是两个类似问题中的第二个问题。如果你解决了这个问题,你就可以破解它。但只有解决了这两个问题,才能破解前一个问题。
给你一棵有 $$$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
注意
第一个示例的配置如下所示,这是不可能实现的。
第二个示例的操作顺序如下所示。