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 行に出力せよ.

제한

힌트