[省选联考 2020 A 卷] 树

题目描述

给定一棵 $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\limits_{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$。 $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$。