题目描述

给定一棵有 $n$ 个节点的树。每个节点有一个点权和一个参数。节点 $i$ 的权值为 $w_i$，参数为 $c_i$。$1$ 是这棵树的根。

现在，对每个节点 $u$（$1 \leq u \leq n$），请在树上你找到最长的一条链 $v_1, v_2, \dots v_m$，满足如下条件：

1. $v_1 = u$。
2. 对 $2 \leq i \leq m$， 有 $v_i$ 是 $v_{i - 1}$ 的父节点。
3. 链上节点的点权和不超过 $c_u$，即 $\sum_{j = 1}^m w_{v_j} \leq c_u$。

输入格式

第一行是一个整数，表示树的节点数 $n$。
第二行有 $n - 1$ 个整数 $p_2, p_3, \dots p_n$，其中 $p_i$ 表示节点 $i$ 的父节点。
第三行有 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的权值 $w_i$。
第四行有 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的参数 $c_i$。

输出格式

输出一行 $n$ 个用空格隔开的整数，第 $i$ 个整数表示节点 $i$ 对应的链的最长长度。

5
1 1 2 2
1 2 3 4 5
1 3 3 6 8

1 2 1 2 3

提示

数据规模与约定

对全部的测试点，保证 $1 \leq u, v \leq n \leq 10^5$，$1 \leq p_i \lt i$，$1 \leq w_i \leq c_i \leq 10^9$。