#arc063c. [arc063_c]Integers on a Tree
[arc063_c]Integers on a Tree
問題文
頂点の木があり、頂点には と番号が振られています。 () 番目の辺は頂点 と頂点 を結んでいます。
高橋君は木の 個の頂点に整数を書き込みました。具体的には、各 について、頂点 に整数 を書き込みました。その後、高橋君は居眠りを始めました。
木を見つけた青木君は、残りのすべての頂点に整数を書き込み、高橋君を驚かせようとしています。高橋君を驚かせるためには、木が次の条件を満たさなければなりません。
- 条件: 辺で直接結ばれた つの頂点に書かれている整数の差がちょうど である。
残りのすべての頂点に書き込む整数を工夫することで、木が条件を満たすようにできるか判定してください。もし可能な場合は、どのように整数を書き込めばよいかを具体的にひとつ求めて下さい。
制約
- ()
- () (21:18, 制約の誤記を修正)
- ()
- 与えられるグラフは木になることが保証される
- はすべて相異なる
入力
入力は以下の形式で標準入力から与えられる。
出力
残りのすべての頂点に書き込む整数を工夫することで木が条件を満たすようにできるならば Yes
を、できないならば No
を出力せよ。
条件を満たせる場合、追加で 行出力せよ。このうちの () 行目には、頂点 に書かれる整数を出力せよ。条件を満たすような整数の書き込み方が複数ある場合、そのうちいずれかひとつを出力すればよい。
入力例 1
出力例 1
はじめ、木は以下の図のような状態である。頂点のそばに書かれた数が頂点番号を、頂点の中に書かれた青い数が元から書き込まれていた整数を表す。
青木君はたとえば次のように残りの頂点に整数を書き込むことで木が条件を満たすようにできる。これは出力例 に対応している。
木が条件を満たしていれば、これとは異なった出力でも AC となることに注意せよ。たとえば、入力例 に対しては
という出力でも正答となる。
入力例 2
出力例 2
入力例 3
出力例 3
新たに書き込む整数は負になったり を超えたりしても構わない。