Background

The school is organizing a banquet.

Lianzi and Meili found that the school’s structure is very complex. Among students, there are relationships of departments and supervisors. Inside each department, the supervisor relationship forms a single chain. The student with the highest rank in one department may also be restricted by some student in another department.

Lianzi and Meili also attend the banquet. But they have their own ways to judge the attending students. For example, they like some departments more and are not interested in others. They also have different opinions about students at different ranks.

As described in a classic problem, every student does not want to attend the banquet together with their direct supervisor.

Meili wants to know, in the best case, how many students attending the banquet are liked by her.

Problem Description

The student society can be seen as a node array arranged into an isosceles right triangle. This node array has $n$ rows, and row $i$ has $i$ nodes. We label the node in row $i$ and column $j$ as $(i,j)$.

• These nodes have weights. Specifically, the weight of node $(i,j)$ is $r_i\oplus c_j$, where $r$ and $c$ are given $01$ sequences, and $\oplus$ is the bitwise XOR operation.
• These nodes are connected by edges. Specifically, for $1\le i< n$, $1\le j\le i$, there is an edge connecting $(i,j)$ and $(i+1,j)$. In addition, for $2\le i\le n$, there is also an edge connecting $(i,i)$ and $(i-1,a_i)$. Here, $a$ is a given sequence.

Now you need to choose some nodes such that no two chosen nodes are connected by an edge, and maximize the sum of weights of the chosen nodes.

The figure below shows an example with $n=8$. Black nodes have weight $1$, and white nodes have weight $0$.

Note: The picture only symbolically shows part of the values of $r_i$ and $c_i$. The actual values in the picture are $\def\t{,\allowbreak}r=\{1\t 1\t 0\t 1\t 0\t 0\t 0\t 1\}\t c=\{0\t 0\t 1\t 0\t 1\t 1\t 0\t 0\}$.

Input Format

• The first line contains a positive integer $n$, describing the size of the node array.
• The second line contains $n$ integers $0$ or $1$, describing the values of $r_i$.
• The third line contains $n$ integers $0$ or $1$, describing the values of $c_i$.
• The fourth line contains $n-1$ positive integers, where the $i$-th number describes the value of $a_{i+1}$.

Output Format

• Output one integer in a single line, describing the maximum possible sum of weights of the selected nodes.

8
1 1 0 1 0 0 0 1
0 0 1 0 1 1 0 0
1 1 3 2 2 1 4

14

Hint

Sample Explanation

One possible selection is shown in the figure below. The orange-red blocks indicate the selected nodes.

Constraints and Notes

For all testdata, it is guaranteed that $1\le n\le 10^6$, $r_i\in\{0,1\}$, $c_i\in\{0,1\}$, $1\le a_i<i$.

Translated by ChatGPT 5