P1612 [yLOI2018] Chains on a Tree

Given a tree with $n$ nodes. Each node has a weight and a parameter. For node $i$, its weight is $w_i$ and its parameter is $c_i$. Node $1$ is the root. Now, for each node $u$ ($1 \leq u \leq n$), find the longest chain $v_1, v_2, \dots v_m$ on the tree that satisfies the following conditions: 1. $v_1 = u$. 2. For $2 \leq i \leq m$, $v_i$ is the parent of $v_{i - 1}$. 3. The sum of weights on the chain does not exceed $c_u$, i.e., $\sum_{j = 1}^m w_{v_j} \leq c_u$.

The first line contains an integer $n$, the number of nodes in the tree. The second line contains $n - 1$ integers $p_2, p_3, \dots p_n$, where $p_i$ denotes the parent of node $i$. The third line contains $n$ integers; the $i$-th integer is the weight $w_i$ of node $i$. The fourth line contains $n$ integers; the $i$-th integer is the parameter $c_i$ of node $i$.

Output one line with $n$ space-separated integers. The $i$-th integer denotes the maximum length of the chain corresponding to node $i$.

Constraints For all testdata, it is guaranteed that $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$. Translated by ChatGPT 5