P6623 [NOI Qualifier Joint Contest 2020 Paper A] Tree

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)$.

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$.

Only one line containing one integer, representing the answer.

[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