QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[0]

# 6160. 树

Statistics

给定一棵 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

接下来一行 n1 个正整数,依次表示 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% 的数据:1n2501

40% 的数据:1n152501

另有 20% 的数据:所有 pi=i1(2in)

另有 20% 的数据:所有 vi=1(1in)

100% 的数据:1n,vi525010,1pin