CF1059E Split the Tree

给定一棵有 $n$ 个结点的有根树，根为编号为 $1$ 的结点。第 $i$ 个结点上有一个数 $w_i$。请将这棵树划分为尽可能少的“竖直路径”，使得每条路径包含的结点数不超过 $L$，且每条路径上所有 $w_i$ 的和不超过 $S$。每个结点必须且只能属于一条路径。 一条“竖直路径”定义为一组结点 $v_1, v_2, \ldots, v_k$，其中 $v_i$（$i \ge 2$）是 $v_{i-1}$ 的父结点。

第一行包含三个整数 $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 < i$），其中 $p_i$ 表示第 $i$ 个结点的父结点编号。

输出一个整数，表示最少需要多少条竖直路径。如果无法划分，输出 $-1$。

在第一个样例中，树被划分为 $\{1\},\ \{2\},\ \{3\}$。 在第二个样例中，树可以划分为 $\{1,\ 2\},\ \{3\}$ 或 $\{1,\ 3\},\ \{2\}$。 在第三个样例中，无法划分该树。 由 ChatGPT 4.1 翻译