【统一省选2020】树 - 题目 - Universal Online Judge

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

设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_{1}, c_{2}, \dots, c_{k}$ ，定义 $x$ 的价值为：

$v a l (x) = (v_{c_{1}} + d (c_{1}, x)) \oplus (v_{c_{2}} + d (c_{2}, x)) \oplus \dots \oplus (v_{c_{k}} + d (c_{k}, x))$

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

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

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

第二行 $n$ 个正整数表示 $v_{i}$ 。

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

一行一个整数表示答案。

5
5 4 1 2 3
1 1 2 2

$v a l (1) = (5 + 0) \oplus (4 + 1) \oplus (1 + 1) \oplus (2 + 2) \oplus (3 + 2) = 3$ 。

$v a l (2) = (4 + 0) \oplus (2 + 1) \oplus (3 + 1) = 3$ 。

$v a l (3) = (1 + 0) = 1$ 。

$v a l (4) = (2 + 0) = 2$ 。

$v a l (5) = (3 + 0) = 3$ 。

和为 $12$ 。

见附加文件中 ex_tree2.in 与 ex_tree2.ans。

对于前 $10 %$ 的数据： $1 \leq n \leq 2501$ 。

对于前 $40 %$ 的数据： $1 \leq n \leq 152501$ 。

另有 $20 %$ 的数据：所有 $p_{i} = i - 1 (2 \leq i \leq n)$ 。

另有 $20 %$ 的数据：所有 $v_{i} = 1 (1 \leq i \leq n)$ 。

对于 $100 %$ 的数据： $1 \leq n, v_{i} \leq 525010, 1 \leq p_{i} \leq n$ 。

时间限制: $2 s$

空间限制: $512 MB$

Universal Online Judge