24181번 - クッキーゲーム 다국어

N 頂点の無向木があり，各頂点には 1 から N までの番号が付けられている．また，各頂点には，1 枚または 2 枚のクッキーが置かれている．

あなたは，この木を使ってゲームを行うことにした．はじめに，あなたは木の頂点を 1 つ選び，その頂点に駒を 1 つ置く．その後，次の行動を，ゲームが終わるまで繰り返す．

• 現在駒が置かれている頂点にあるクッキーを，1 枚だけ食べる．さらに，現在駒が置かれている頂点に隣接する頂点を 1 つ選び，その頂点に駒を移動させる．移動先の頂点にクッキーが 1 枚も置かれていない場合，その時点でゲームは終了となる．

あなたが最適に行動したとき，ゲーム中，最大で何枚のクッキーを食べることができるだろうか．

入力は 50 個以下のデータセットからなる． 各データセットは次の形式で表される．

N
x1x2...xN
p1
p2
…
pN-1

1 行目には，木の頂点数 N (2 ≤ N ≤ 10⁵) が与えられる．2 行目は 1 または 2 のみからなる N 文字の文字列が与えられる．このうち i 番目の文字 x_i は，はじめに頂点 i に置かれているクッキーの枚数を表す．3 行目からの N-1 行には，木の頂点の隣接情報が与えられる．このうち j 行目に与えられる整数 p_j (1 ≤ p_j ≤ j) は，頂点 j+1 と 頂点 p_j が隣接していることを表す．

入力の終わりは 1 つのゼロからなる行で表される．

各データセットに対し，あなたがゲーム中に食べることのできるクッキーの枚数の最大値を，1 行に出力せよ．