#P13099. [FJCPC 2025] VERTeX
[FJCPC 2025] VERTeX
题目描述
给定一棵有 个结点的树,结点依次以 标号。第 ()个结点有正整数权值 。对于连接结点 与 的树边,其边权为 。
现在给定树的形态与每条树边的边权,你需要判断是否存在满足条件的一组结点权值。若存在,则求出任意一组结点权值。
输入格式
第一行,一个正整数 (),表示结点数量。
接下来 行,每行三个整数 (,),表示一条连接结点 与 的边权为 的树边。
输出格式
若满足条件的一组结点权值不存在,则输出一行一个字符串 NO
。
否则,第一行输出一个字符串 YES
,第二行输出 个正整数 ,表示你求出的一组结点权值。你需要保证对于任意 有 。
若存在多组满足条件的答案,输出任意一组均可。
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
提示
对于第一组样例,可以验证给出的权值满足条件。注意到 ,因此 与 只能取 ,继而可以确定其他结点的权值。
对于第二组样例,注意到 $b_2 + b_3 = w_{23} = 9 = w_{12} + w_{34} = b_1 + b_2 + b_3 + b_4$,从而 ,而这与 且 矛盾,因此不存在满足条件的结点权值。