クッキーゲーム
시간 제한8초메모리 제한1024 MB
각 정점에 쿠키가 1개 또는 2개 놓인 트리에서 아무 정점에서 시작해 이동하며 쿠키를 하나씩 먹고, 빈 정점으로 이동하면 끝날 때 먹을 수 있는 쿠키 수의 최댓값을 구한다.
문제
N 頂点の無向木があり，各頂点には 1 から N までの番号が付けられている．また，各頂点には，1 枚または 2 枚のクッキーが置かれている．
あなたは，この木を使ってゲームを行うことにした．はじめに，あなたは木の頂点を 1 つ選び，その頂点に駒を 1 つ置く．その後，次の行動を，ゲームが終わるまで繰り返す．
- 現在駒が置かれている頂点にあるクッキーを，1 枚だけ食べる．さらに，現在駒が置かれている頂点に隣接する頂点を 1 つ選び，その頂点に駒を移動させる．移動先の頂点にクッキーが 1 枚も置かれていない場合，その時点でゲームは終了となる．
あなたが最適に行動したとき，ゲーム中，最大で何枚のクッキーを食べることができるだろうか．
입력
入力は 50 個以下のデータセットからなる． 各データセットは次の形式で表される．
N
x1x2...xN
p1
p2
…
pN-1
1 行目には，木の頂点数 N (2 ≤ N ≤ 105) が与えられる．2 行目は 1 または 2 のみからなる N 文字の文字列が与えられる．このうち i 番目の文字 xi は，はじめに頂点 i に置かれているクッキーの枚数を表す．3 行目からの N-1 行には，木の頂点の隣接情報が与えられる．このうち j 行目に与えられる整数 pj (1 ≤ pj ≤ j) は，頂点 j+1 と 頂点 pj が隣接していることを表す．
入力の終わりは 1 つのゼロからなる行で表される．
출력
各データセットに対し，あなたがゲーム中に食べることのできるクッキーの枚数の最大値を，1 行に出力せよ．