#agc034e. [agc034_e]Complete Compress

[agc034_e]Complete Compress

問題文

頂点に番号 1,2,...,N1, 2, ..., N がついた NN 頂点の木が与えられます。ii 番目の辺は頂点 aia_i と頂点 bib_i を結んでいます。 また長さ NN0, 1 からなる文字列 SS が与えられ、SSii 文字目は頂点 ii に置いてあるコマの個数を表しています。

すぬけ君は、以下の操作を好きなだけ行います。

  • 距離が 22 以上離れたコマ 22 個を選び、お互いに 11 ずつ近づける。 正確に述べると、コマの置かれた頂点 u,vu, v を選び、u,vu, v 間の最短パスを考える。ここでパスの辺数が 22 以上となるように選ぶことにする。パスにおいて uu に隣り合う頂点にコマを 11uu から動かし、vv に隣り合う頂点にコマを 11vv から動かす。

すぬけ君はこれを繰り返し、すべてのコマを同じ頂点に集めたいです。このようなことは可能でしょうか? 可能な場合、それを達成するのに必要な操作の最小回数も求めてください。

制約

  • 2leqNleq20002 \\leq N \\leq 2000
  • S=N|S| = N
  • SS0, 1からなり、また少なくとも 11 文字は 1 を含む
  • 1leqai,bileqN(aineqbi)1 \\leq a_i, b_i \\leq N(a_i \\neq b_i)
  • (a1,b1),(a2,b2),...,(aN1,bN1)(a_1, b_1), (a_2, b_2), ..., (a_{N - 1}, b_{N - 1}) は木をなす

入力

入力は以下の形式で標準入力から与えられる。

NN SS a1a_1 b1b_1 a2a_2 b2b_2 :: aN1a_{N - 1} bN1b_{N - 1}

出力

コマを同じ頂点に集められない場合 -1、集められる場合は操作の最小回数を出力せよ。


入力例 1

7
0010101
1 2
2 3
1 4
4 5
1 6
6 7

出力例 1

  • 頂点 3,53, 5 のコマを選ぶ
  • 頂点 2,72, 7 のコマを選ぶ
  • 頂点 4,64, 6 のコマを選ぶ

33 回の操作ですべてのコマを頂点 11 に集めることができます。


入力例 2

7
0010110
1 2
2 3
1 4
4 5
1 6
6 7

出力例 2

-1

入力例 3

2
01
1 2

出力例 3