A22608.树上的链
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
给定一棵有 n 个节点的树。每个节点有一个点权和一个参数。节点 i 的权值为 wi,参数为 ci。1 是这棵树的根。
现在,对每个节点 u(1≤u≤n),请在树上你找到最长的一条链 v1,v2,…vm,满足如下条件:
- v1=u。
- 对 2≤i≤m, 有 vi 是 vi−1 的父节点。
- 链上节点的点权和不超过 cu,即 ∑j=1mwvj≤cu。
输入格式
第一行是一个整数,表示树的节点数 n。
第二行有 n−1 个整数 p2,p3,…pn,其中 pi 表示节点 i 的父节点。
第三行有 n 个整数,第 i 个整数表示节点 i 的权值 wi。
第四行有 n 个整数,第 i 个整数表示节点 i 的参数 cu。
输出格式
输出一行 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≤u,v≤n≤105,1≤pi<i,1≤wi≤ci≤109。