A2895. 树上的链
编程题
普及/提高-
知识点
题目描述
给定一棵有 $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$。
现在，对每个节点 $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_u$。
第二行有 $n - 1$ 个整数 $p_2, p_3, \dots p_n$，其中 $p_i$ 表示节点 $i$ 的父节点。
第三行有 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的权值 $w_i$。
第四行有 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的参数 $c_u$。
输出格式
输出一行 $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$。
对全部的测试点，保证 $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$。