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

给你一棵包含 $n$ 个顶点的有根树，其根节点为编号 $1$ 的顶点。第 $i$ 个顶点上有一个数值 $w_i$。请将这棵树划分成尽可能少的若干条竖直路径（vertical paths），使得每条路径包含的顶点数不超过 $L$，且每条路径上所有顶点的数值 $w_i$ 之和不超过 $S$。每个顶点必须且仅属于一条路径。

一条竖直路径是指一个顶点序列 $v_1, v_2, \ldots, v_k$，其中对任意 $i \ge 2$，$v_i$ 是 $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 \lt i$), where $p_i$ is the parent of the $i$-th vertex in the tree.

第一行包含三个整数 $n$、$L$、$S$（$1 \le n \le 10^5$，$1 \le L \le 10^5$，$1 \le S \le 10^{18}$）—— 分别表示树的顶点数、单条路径中顶点的最大数量以及单条路径中顶点权值和的最大值。

第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$1 \le w_i \le 10^9$）—— 表示树中各顶点上的数值。

第三行包含 $n - 1$ 个整数 $p_2, \ldots, p_n$（$1 \le p_i \lt i$），其中 $p_i$ 表示树中第 $i$ 个顶点的父节点。

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

输出一个数字——垂直路径的最少数量。如果无法将树分割，输出 $-1$。

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.

在第一个样例中，树被分割为 $\{1\},\ \{2\},\ \{3\}$。

在第二个样例中，树被分割为 $\{1,\ 2\},\ \{3\}$ 或 $\{1,\ 3\},\ \{2\}$。

在第三个样例中，无法分割该树。