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

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Payphone_X

题目描述

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

x 号结点的子树内(包含 x 自身)的所有结点编号为 c_1, c_2, \dots, 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

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

和为 12

样例 2

见附加文件中 tree2.intree2.ans

数据范围与提示

10\% 的数据: 1\le n\le 2501

40\% 的数据: 1\le n\le 152501

另有 20\% 的数据:所有 p_i = i - 1 (2\le i\le n)

另有 20\% 的数据:所有 v_i = 1 (1\le i\le n)

100\% 的数据: 1\le n, v_i \le 525010, 1\le p_i\le n