#3303. 「联合省选 2020 A」树

题目描述

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

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

$$\text{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 \text{val}(i)$ 的结果。

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

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

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

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

输入

5
5 4 1 2 3
1 1 2 2

输出

解释

$\text{val}(1) = (5 + 0) \oplus (4 + 1) \oplus (1 + 1) \oplus (2 + 2) \oplus (3 + 2) = 3$
$\text{val}(2) = (4 + 0) \oplus (2 + 1) \oplus (3 + 1) = 3$
$\text{val}(3) = (1 + 0) = 1$
$\text{val}(4) = (2 + 0) = 2$
$\text{val}(5) = (3 + 0) = 3$
和为 $12$