Description

Given a rooted tree $T$ with $n$ nodes. The nodes are numbered starting from $1$. The root is node $1$. Each node has a positive integer weight $v_i$.

Let the node numbers of all nodes in the subtree of node $x$ (including $x$ itself) be $c_1,c_2,\dots,c_k$. Define the value of $x$ as:

$val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x))$

Here, $d(x,y)$ denotes the number of edges on the unique simple path between nodes $x$ and $y$ in the tree, and $d(x, x) = 0$. $\oplus$ denotes the XOR operation.

Please compute $\sum\limits_{i=1}^n val(i)$.

Input Format

The first line contains a positive integer $n$, representing the size of the tree.

The second line contains $n$ positive integers, representing $v_i$.

The next line contains $n-1$ positive integers, in order representing the parent index $p_i$ of nodes $2$ to $n$.

Output Format

Only one line containing one integer, representing the answer.

5
5 4 1 2 3
1 1 2 2

12

Hint

[Sample Explanation 1]

$val(1)=(5+0)\oplus(4+1)\oplus(1+1)\oplus(2+2)\oplus(3+2)=3$.

$val(2)=(4+0)\oplus(2+1)\oplus(3+1) = 3$.

$val(3)=(1+0)=1$.

$val(4)=(2+0)=2$.

$val(5)=(3+0)=3$.

The sum is $12$.

[Constraints]

For $10\%$ of the testdata: $1\leq n\leq 2501$.

For $40\%$ of the testdata: $1\leq n\leq 152501$.

Another $20\%$ of the testdata: all $p_i=i-1$ ($2\leq i\leq n$).

Another $20\%$ of the testdata: all $v_i=1$ ($1\leq i\leq n$).

For $100\%$ of the testdata: $1\leq n,v_i \leq 525010$, $1\leq p_i\leq n$.

Translated by ChatGPT 5