树上归零(Zeroing the Tree)

题目描述

给定一棵有 $n$ 个结点的树，$1$ 号点为根。树上每个点都有一个值，其中第 $i$ 个点的值为 $a_i$。小爱想通过若干步操作将树上的所有值全部变为 $0$，每步操作可以选择树上任意一个结点 $u$，然后将 $u$ 的子树上的所有值增加 $1$，或者将 $u$ 的子树上的所有值减少 $1$。

请问小爱最少需要几步操作才能将树上所有点的数值变成 $0$？

输入格式

• 第一行：单个整数 $n$；
• 第二行：$n-1$ 个整数 $p_2,\dots,p_n$，表示 2 号点到 n 号点各自的父亲编号；
• 第三行：$n$ 个整数 $a_i$，表示每个点的初始值。

输出格式

• 单个整数：表示最少的操作步数使得所有值归零。

样例输入 #1

3
1 1
10 -10 10

样例输出 #1

30

数据范围

• $-10^9\le a_i\le 10^9$；
• 对于 $30\%$ 的数据：$1\le n\le 100$；
• 对于 $60\%$ 的数据：$1\le n\le 5000$；
• 对于 $100\%$ 的数据：$1\le n\le 100000$。

知识点与难度

本题涉及的知识点从属于 GESP 六级（树、贪心、差分），难度等级：⭐⭐⭐。

测试点分布