← 返回题目列表

Codeforces · 1098/A

A. 树中的总和

中文机器翻译题面 查看原题

Mitya 有一个有根树,其 $$$n$$$ 顶点索引从 $$$1$$$ 到 $$$n$$$,其中根的索引为 $$$1$$$。每个顶点 $$$v$$$ 最初都写有一个整数 $$$a_v \ge 0$$$ 。对于每个顶点 $$$v$$$,Mitya 计算了 $$$s_v$$$:从顶点 $$$v$$$ 到根的路径上写入的所有顶点值的总和,以及 $$$h_v$$$ - 顶点 $$$v$$$ 的深度,表示从顶点 $$$v$$$ 到根的路径上的顶点数量。显然,$$$s_1=a_1$$$ 和 $$$h_1=1$$$。

然后 Mitya 删除了所有数字 $$$a_v$$$,并且意外地他还删除了深度为偶数的顶点(偶数 $$$h_v$$$ 的顶点)的所有值 $$$s_v$$$。您的任务是恢复每个顶点的值 $$$a_v$$$,或者确定 Mitya 犯了错误。如果有多种方法可以恢复这些值,您需要找到一种方法来最小化树中所有顶点的值 $$$a_v$$$ 的总和。

输入

第一行包含一个整数 $$$n$$$ — 树中的顶点数 ($$$2 \le n \le 10^5$$$)。以下行包含整数 $$$p_2$$$、$$$p_3$$$、... $$$p_n$$$,其中 $$$p_i$$$ 代表树中索引为 $$$i$$$ 的顶点的父节点 ($$$1 \le p_i < i$$$)。最后一行包含整数值 $$$s_1$$$、$$$s_2$$$、...、$$$s_n$$$ ($$$-1 \le s_v \le 10^9$$$),其中删除的值将替换为 $$$-1$$$。

输出

输出一个整数——原始树中所有值 $$$a_v$$$ 的最小总和,如果该树不存在,则输出 $$$-1$$$。

示例

输入 #1

5
1 1 1 1
1 -1 -1 -1 -1

输出 #1

1

输入 #2

5
1 2 3 1
1 -1 2 -1 -1

输出 #2

2

输入 #3

3
1 2
2 -1 1

输出 #3

-1