[yLOI2018] 树上的链

题目描述

给定一棵有 $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$ 对应的链的最长长度。

输入输出样例

输入样例 #1

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

输出样例 #1

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$。