AGC010-C Cleaning

問題リンク

問題概要

木があって、頂点には値が割り振られている。 葉を2つ選んでその間のパスの頂点の値をインクリメントする、という操作を、最初全部値が0の状態から始めてこの状態を構成できるか。

解説

頂点ベースではなく、辺ベースで考えると、ある葉以外の頂点の接続する辺の重みの和は、頂点の値の2倍になる必要がある。 この条件を満たすように辺に重みを割り当てたいが、これは葉から適当にDFSしていけばできる。 負の重みの辺があってはならず、頂点の重みより重い辺があってもならないので、もしこうなってしまったら"NO"と出力すれば良い。