Cookie Game

There is an undirected tree with $N$ vertices, numbered 1 through $N$. Each vertex has either one or two cookies on it.

You play a game on this tree. First, you choose one vertex and place a piece on it. Then you repeat the following action until the game ends.

• Eat exactly one cookie on the vertex where the piece currently is. Then choose a vertex adjacent to the current one and move the piece there. If the destination has no cookies left, the game ends at that moment.

If you play optimally, what is the maximum number of cookies you can eat during the game?

The input contains at most 50 datasets. Each dataset has the following format.

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

The first line gives the number of vertices $N$ ($2 \le N \le 10^5$). The second line is a string of $N$ characters, each 1 or 2. The $i$-th character $x_i$ is the number of cookies initially on vertex $i$. The next $N-1$ lines give the adjacency information. The integer $p_j$ on line $j$ ($1 \le p_j \le j$) means that vertex $j+1$ is adjacent to vertex $p_j$.

The input ends with a line containing a single zero.

For each dataset, print on one line the maximum number of cookies you can eat during the game.