题目描述

给定一棵 $n$ 个结点的树，$1$ 号点为根。每个点都有一个权值，第 $i$ 个点的权值为 $a_i$，权值有正有负。请在这棵树里找到一个连通分量，该连通分量内结点的权值之和达到最大，输出这个最大和。

连通分量是指树上一些点的集合，如果用树上的边连接这些点不需要经过连通分量外的点。连通分量可以是空集，空集的权值之和定义为 $0$。

输入格式

• 第一行：单个整数表示 $n$；
• 第二行：$n-1$ 个整数表示 $p_2$ 到 $p_n$，$p_i$ 表示 $i$ 号点父亲的编号，保证有 $1\leq p_i<i$
• 第三行：$n$ 个整数表示 $a_1$ 到 $a_n$，$a_i$ 表示 $i$ 号点的权值

输出格式

• 单个整数：表示答案。

6
1 1 2 2 3
10 20 -30 40 -50 60

100

样例解释 1

10+20-30+40+60=100

数据范围

• 对于 $30\%$ 的数据， $n\leq 200$；
• 对于 $60\%$ 的数据， $n\leq 5000$；
• 对于 $100\%$ 的数据， $1\leq n\leq 200,000$
• $-1,000,000,000\leq a_i\leq 1,000,000,000$。