#P1612. [yLOI2018] 树上的链

[yLOI2018] 树上的链

题目描述

给定一棵有 nn 个节点的树。每个节点有一个点权和一个参数。节点 ii 的权值为 wiw_i,参数为 cic_i11 是这棵树的根。

现在,对每个节点 uu1un1 \leq u \leq n),请在树上你找到最长的一条链 v1,v2,vmv_1, v_2, \dots v_m,满足如下条件:

  1. v1=uv_1 = u
  2. 2im2 \leq i \leq m, 有 viv_ivi1v_{i - 1} 的父节点。
  3. 链上节点的点权和不超过 cuc_u,即 j=1mwvjcu\sum_{j = 1}^m w_{v_j} \leq c_u

输入格式

第一行是一个整数,表示树的节点数 nn
第二行有 n1n - 1 个整数 p2,p3,pnp_2, p_3, \dots p_n,其中 pip_i 表示节点 ii 的父节点。
第三行有 nn 个整数,第 ii 个整数表示节点 ii 的权值 wiw_i
第四行有 nn 个整数,第 ii 个整数表示节点 ii 的参数 cuc_u

输出格式

输出一行 nn 个用空格隔开的整数,第 ii 个整数表示节点 ii 对应的链的最长长度。

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

提示

数据规模与约定

对全部的测试点,保证 1u,vn1051 \leq u, v \leq n \leq 10^51pi<i1 \leq p_i \lt i1wici1091 \leq w_i \leq c_i \leq 10^9