You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

给定一棵 $n$ 个点的有根树，其中节点 $1$ 为根，节点 $i~(2\le i\le n)$ 的父亲为 $f_i$。

有 $n$ 个任务，第 $i$ 个任务的耗时为 $t_i$。你需要将这 $n$ 个任务分配给 $n$ 个节点，满足每个节点恰好完成一个任务。于此同时，每个节点均有一个限制，节点 $i~(1\le i\le n)$ 的限制为 $w_i$，要求在节点 $i$ 的子树内的所有任务的耗时均不能超过 $w_i$。

现在，你可以选择一个节点，并将其的限制增加 $k$，其中 $k$ 为任意非负整数，你需要求出最小的 $k$，使得在增大一个节点的限制后，存在一种任务分配的方案满足所有限制，保证存在至少一种增加限制的方案使得存在一种任务分配的方案满足所有限制。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$，表示树的点数与任务的个数。

输入的第二行包含 $n-1$ 个正整数 $f_2,...,f_n$，表示 $2\sim n$ 号节点的父亲。

输入的第三行包含 $n$ 个正整数 $t_1,t_2,...,t_n$，表示每个任务的耗时。

输入的第四行包含 $n$ 个正整数 $w_1,w_2,...,w_n$，表示每个节点的限制。

输出格式

输出到标准输出。

输出一行一个非负整数 $k$，表示限制增量的最小值。

6
1 2 2 1 5
1 2 2 3 5 6
6 1 3 3 5 1

2

样例 1 解释

一种可行的方案为：将节点 $2$ 的限制增加 $2$ 后，将耗时为 $6,3,2,2,5,1$ 的任务依次分配给节点 $1\sim 6$。

子任务

对于所有测试数据，保证 $1\le n\le 10^5,~1\le f_i<i,~1\le t_1\le t_2\le ...\le t_n\le n,~1\le w_i\le n$。保证存在至少一种增加限制的方案使得存在一种任务分配的方案满足所有限制。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。