#P13099. [FJCPC 2025] VERTeX

    ID: 12849 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>2025福建Special Judge树论XCPC

[FJCPC 2025] VERTeX

题目描述

给定一棵有 nn 个结点的树,结点依次以 1,2,,n1, 2, \dots, n 标号。第 ii1in1\leq i\leq n)个结点有正整数权值 bi>0b_i > 0。对于连接结点 uuvv 的树边,其边权为 wuv=bu+bvw_{uv} = b_u + b_v

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

输入格式

第一行,一个正整数 nn1n2×1051\leq n\leq 2\times 10^5),表示结点数量。

接下来 n1n - 1 行,每行三个整数 u,v,wuvu, v, w_{uv}1u,vn1\leq u,v\leq n1wuv1091\leq w_{uv}\leq 10^9),表示一条连接结点 uuvv 的边权为 wuvw_{uv} 的树边。

输出格式

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

否则,第一行输出一个字符串 YES,第二行输出 nn 个正整数 b1,,bnb_1, \dots, b_n,表示你求出的一组结点权值。你需要保证对于任意 1in1\leq i\leq nbi109b_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

提示

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

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