题目描述

给定一棵有 $n$ 个结点的树，结点依次以 $1, 2, \dots, n$ 标号。第 $i$（$1\leq i\leq n$）个结点有正整数权值 $b_i > 0$。对于连接结点 $u$ 与 $v$ 的树边，其边权为 $w_{uv} = b_u + b_v$。

现在给定树的形态与每条树边的边权，你需要判断是否存在满足条件的一组结点权值。若存在，则求出任意一组结点权值。

输入格式

第一行，一个正整数 $n$（$1\leq n\leq 2\times 10^5$），表示结点数量。

接下来 $n - 1$ 行，每行三个整数 $u, v, w_{uv}$（$1\leq u,v\leq n$，$1\leq w_{uv}\leq 10^9$），表示一条连接结点 $u$ 与 $v$ 的边权为 $w_{uv}$ 的树边。

输出格式

若满足条件的一组结点权值不存在，则输出一行一个字符串 NO。

否则，第一行输出一个字符串 YES，第二行输出 $n$ 个正整数 $b_1, \dots, b_n$，表示你求出的一组结点权值。你需要保证对于任意 $1\leq i\leq n$ 有 $b_i \leq 10^9$。

若存在多组满足条件的答案，输出任意一组均可。

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

YES
3 2 1 1 5

4
1 2 5
2 3 9
3 4 4

NO

提示

对于第一组样例，可以验证给出的权值满足条件。注意到 $w_{34} = b_3 + b_4 = 2$，因此 $b_3$ 与 $b_4$ 只能取 $1$，继而可以确定其他结点的权值。

对于第二组样例，注意到 $b_2 + b_3 = w_{23} = 9 = w_{12} + w_{34} = b_1 + b_2 + b_3 + b_4$，从而 $b_1 + b_4 = 0$，而这与 $b_1 > 0$ 且 $b_4 > 0$ 矛盾，因此不存在满足条件的结点权值。