Split the Tree

2000ms

262144K

Description:

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:

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:

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

Sample Input:

3 1 3
1 2 3
1 1

Sample Output:

Sample Input:

3 3 6
1 2 3
1 1

Sample Output:

Sample Input:

1 1 10000
10001

Sample 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.

Informação

Provedor Codeforces

Código CF1059E