给定一棵 n 个结点的有根树 T,结点从 1 开始编号,根结点为 1 号结点,每个结点有一个正整数权值 vi。
设 x 号结点的子树内(包含 x 自身)的所有结点编号为 c1,c2,…,ck,定义 x 的价值为:
val(x)=(vc1+d(c1,x))⊕(vc2+d(c2,x))⊕⋯⊕(vck+d(ck,x))
其中 d(x,y) 表示树上 x 号结点与 y 号结点间唯一简单路径所包含的边数,d(x,x)=0。⊕ 表示异或运算。
请你求出 ∑ni=1val(i) 的结果。
输入格式
第一行一个正整数 n 表示树的大小。
第二行 n 个正整数表示 vi。
接下来一行 n−1 个正整数,依次表示 2 号结点到 n 号结点,每个结点的父亲编号 pi。
输出格式
仅一行一个整数表示答案。
样例数据
样例 1 输入
5
5 4 1 2 3
1 1 2 2
样例 1 输出
12
样例 1 解释
val(1)=(5+0)⊕(4+1)⊕(1+1)⊕(2+2)⊕(3+2)=3。
val(2)=(4+0)⊕(2+1)⊕(3+1)=3。
val(3)=(1+0)=1。
val(4)=(2+0)=2。
val(5)=(3+0)=3。
和为 12。
样例 2
见下发文件。
子任务
10% 的数据:1≤n≤2501。
40% 的数据:1≤n≤152501。
另有 20% 的数据:所有 pi=i−1(2≤i≤n)。
另有 20% 的数据:所有 vi=1(1≤i≤n)。
100% 的数据:1≤n,vi≤525010,1≤pi≤n。