← 返回题目
题库练习 树上的链
← 上一题 下一题 →

A2895 | 树上的链

来源2018
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一棵有 $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_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
C++ 编辑器
输入
输出