A12100 | Split the Tree

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}$ .

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 one number — the minimum number of vertical paths. If it is impossible to split the tree, output $-1$ .