Triangle Social Network Maximum Independent Set

The student society can be represented as nodes arranged in an isosceles right triangle. There are \(n\) rows, and the \(i\)-th row contains \(i\) nodes. We label the node in the \(i\)-th row and \(j\)-th column as \((i,j)\).

Each node \((i,j)\) has a weight defined as \(r_i \oplus c_j\), where \(r = [r_1, r_2, \dots, r_n]\) and \(c = [c_1, c_2, \dots, c_n]\) are given binary (0-1) sequences and \(\oplus\) denotes the binary XOR operation.

The nodes are connected by edges as follows:

• For \(1 \le i < n\) and \(1 \le j \le i\): there is an edge connecting \((i,j)\) and \((i+1,j)\). (Vertical edge)
• For \(2 \le i \le n\): there is an edge connecting \((i,i)\) and \((i-1, a_i)\), where \(a = [a_2, a_3, \dots, a_n]\) is a given sequence and for each \(i\), \(1 \le a_i \le i-1\). (Extra edge)

Your task is to select a subset of nodes such that no two selected nodes are adjacent (i.e. there is no edge between any two selected nodes) and the sum of their weights is maximized.

Note: All formulas are written in LaTeX format.

inputFormat

The input consists of four parts:

1. An integer \(n\) representing the number of rows.
2. A line containing \(n\) space-separated binary integers representing the sequence \(r_1, r_2, \dots, r_n\).
3. A line containing \(n\) space-separated binary integers representing the sequence \(c_1, c_2, \dots, c_n\).
4. A line containing \(n-1\) space-separated integers representing the sequence \(a_2, a_3, \dots, a_n\). For each \(i\) from 2 to \(n\), \(1 \le a_i \le i-1\).

outputFormat

Output a single integer: the maximum sum of weights of a subset of nodes with no two adjacent nodes.

sample

1
1
0

1