3421. [统一省选 2020]树

【题目描述】

  给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。

  设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1,c_2,\cdots,c_k$，定义 $x$ 的价值为：

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

  其中 $d(x,y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x,x)=0$。$\oplus$表示异或运算。

  请你求出$\sum_{i=1}^n val(i)$的结果。

【输入格式】

第一行一个正整数 $n$ 表示树的大小。

第二行 $n$ 个正整数表示$v_i$。

接下来一行 $n−1$ 个正整数，依次表示 $2$ 号结点到 $n$ 号结点，每个结点的父亲编号$p_i$

【输出格式】

仅一行一个整数表示答案。

【样例1输入】

5
5 4 1 2 3
1 1 2 2

【样例1输出】

12

【样例1解释】

value(1) = (5 + 0)$\oplus$(4 + 1)$\oplus$(1 + 1)$\oplus$(2 + 2)$\oplus$(3 + 2) = 3。

value(2) = (4 + 0)$\oplus$(2 + 1)$\oplus$ (3 + 1) = 3。

value(3) = (1 + 0) = 1。

value(4) = (2 + 0) = 2。

value(5) = (3 + 0) = 3。

和为 12。

【样例2】

见选手目录下的 tree/tree2.in 与 tree/tree2.ans。

【数据范围】

10% 的数据：$1 ≤ n ≤ 2501$。

40% 的数据：$1 ≤ n ≤ 152501$。

另有 20% 的数据：所有$p_i= i − 1（2 ≤ i ≤ n）$。

另有 20% 的数据：所有$v_i = 1（1 ≤ i ≤ n）$。

100% 的数据：$1 ≤ n,v_i ≤ 525010，1 ≤ p_i ≤ n$。

【来源】

HAOI2020 Day2 Task2