#Algo2007. 树

    ID: 295 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>字符串字典树luogu各省省选2020

题目描述

给定一棵 nn 个结点的有根树 TT,结点从 11 开始编号,根结点为 11 号结点,每个结点有一个正整数权值 viv_i

xx 号结点的子树内(包含 xx 自身)的所有结点编号为 c1,c2,,ckc_1,c_2,\dots,c_k,定义 xx 的价值为:

$ 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)d(x,y) 表示树上 xx 号结点与 yy 号结点间唯一简单路径所包含的边数,d(x,x)=0d(x, x) = 0\oplus 表示异或运算。

请你求出 i=1nval(i)\sum\limits_{i=1}^n val(i) 的结果。

输入格式

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

第二行 nn 个正整数表示 viv_i

接下来一行 n1n-1 个正整数,依次表示 22 号结点到 nn 号结点,每个结点的父亲编号 pip_i

输出格式

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

5
5 4 1 2 3
1 1 2 2
12

提示

【样例解释 11

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

val(2)=(4+0)(2+1)(3+1)=3val(2)=(4+0)\oplus(2+1)\oplus(3+1) = 3

val(3)=(1+0)=1val(3)=(1+0)=1

val(4)=(2+0)=2val(4)=(2+0)=2

val(5)=(3+0)=3val(5)=(3+0)=3

和为 1212

【数据范围】

对于 10%10\% 的数据:1n25011\leq n\leq 2501

对于 40%40\% 的数据:1n1525011\leq n\leq 152501

另有 20%20\% 的数据:所有 pi=i1p_i=i-12in2\leq i\leq n);

另有 20%20\% 的数据:所有 vi=1v_i=11in1\leq i\leq n);

对于 100%100\% 的数据:1n,vi5250101\leq n,v_i \leq 5250101pin1\leq p_i\leq n