1059E · Split the Tree

Problem: You are given a rooted tree on $n$ vertices, its root is the vertex number $1$. The $i$-th vertex contains a number $w_i$. Split it into the minimum possible number of vertical paths in such a way that each path contains no more than $L$ vertices and the sum of integers $w_i$ on each path does not exceed $S$. Each vertex should belong to exactly one path.

A vertical path is a sequence of vertices $v_1, v_2, \ldots, v_k$ where $v_i$ ($i \ge 2$) is the parent of $v_{i - 1}$.

Input Format: The first line contains three integers $n$, $L$, $S$ ($1 \le n \le 10^5$, $1 \le L \le 10^5$, $1 \le S \le 10^{18}$) — the number of vertices, the maximum number of vertices in one path and the maximum sum in one path.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($1 \le w_i \le 10^9$) — the numbers in the vertices of the tree.

The third line contains $n - 1$ integers $p_2, \ldots, p_n$ ($1 \le p_i < i$), where $p_i$ is the parent of the $i$-th vertex in the tree.

Output Format: Output one number  — the minimum number of vertical paths. If it is impossible to split the tree, output $-1$.

Note: In the first sample the tree is split into $\{1\},\ \{2\},\ \{3\}$.

In the second sample the tree is split into $\{1,\ 2\},\ \{3\}$ or $\{1,\ 3\},\ \{2\}$.

In the third sample it is impossible to split the tree.