AT_agc010_c [AGC010C] Cleaning

[problemUrl]: https://atcoder.jp/contests/agc010/tasks/agc010_c $ N $ 頂点からなる木があり、頂点には $ 1 $ から $ N $ の番号がついています。 また、$ N-1 $ 本の辺の内、$ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 今、各頂点 $ i $ には $ A_i $ 個の石が置いてあります。 以下の操作を繰り返して、全ての石を取り除くことができるか判定してください。 - 相異なる $ 2 $ つの葉を一組選ぶ。そして、その $ 2 $ 頂点間のパス上にある頂点全てからちょうど $ 1 $ つ石を取り除く。 ただし、葉とは木の頂点で次数が $ 1 $ の頂点を指し、選んだ葉自体もパス上の頂点として考える。 石が置かれていない頂点がパス上にあるときは、その操作を行えないことに注意してください。

N/A

N/A

### 制約 - $ 2\ ≦\ N\ ≦\ 10^5 $ - $ 1\ ≦\ a_i,b_i\ ≦\ N $ - $ 0\ ≦\ A_i\ ≦\ 10^9 $ - 与えられるグラフは木である。 ### Sample Explanation 1 以下のようにすれば、すべての石を取り除くことができます。 - 葉として $ 4 $ と $ 5 $ を選ぶ。このとき、$ 4 $ 以外の頂点に石が $ 1 $ 個残る。 - 葉として $ 1 $ と $ 5 $ を選ぶ。このとき、全ての頂点から石がなくなる。