AT_agc034_e [AGC034E] Complete Compress

[problemUrl]: https://atcoder.jp/contests/agc034/tasks/agc034_e 頂点に番号 $ 1,\ 2,\ ...,\ N $ がついた $ N $ 頂点の木が与えられます。$ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 また長さ $ N $ の `0`, `1` からなる文字列 $ S $ が与えられ、$ S $ の $ i $ 文字目は頂点 $ i $ に置いてあるコマの個数を表しています。 すぬけ君は、以下の操作を好きなだけ行います。 - 距離が $ 2 $ 以上離れたコマ $ 2 $ 個を選び、お互いに $ 1 $ ずつ近づける。 正確に述べると、コマの置かれた頂点 $ u,\ v $ を選び、$ u,\ v $ 間の最短パスを考える。ここでパスの辺数が $ 2 $ 以上となるように選ぶことにする。パスにおいて $ u $ に隣り合う頂点にコマを $ 1 $ 個 $ u $ から動かし、$ v $ に隣り合う頂点にコマを $ 1 $ 個 $ v $ から動かす。 すぬけ君はこれを繰り返し、すべてのコマを同じ頂点に集めたいです。このようなことは可能でしょうか？ 可能な場合、それを達成するのに必要な操作の最小回数も求めてください。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 2000 $ - $ |S|\ =\ N $ - $ S $ は `0`, `1`からなり、また少なくとも $ 1 $ 文字は `1` を含む - $ 1\ \leq\ a_i,\ b_i\ \leq\ N(a_i\ \neq\ b_i) $ - 辺 $ (a_1,\ b_1),\ (a_2,\ b_2),\ ...,\ (a_{N\ -\ 1},\ b_{N\ -\ 1}) $ は木をなす ### Sample Explanation 1 \- 頂点 $ 3,\ 5 $ のコマを選ぶ - 頂点 $ 2,\ 7 $ のコマを選ぶ - 頂点 $ 4,\ 6 $ のコマを選ぶ の $ 3 $ 回の操作ですべてのコマを頂点 $ 1 $ に集めることができます。