Split the Tree

题意翻译

现有 $n$ 个点组成一棵以 $1$ 为根的有根树，第 $i$ 个点的点权为 $w_i$，需将其分成若干条垂直路径使得每一个点当且仅当被一条垂直路径覆盖，同时，每条垂直路径点数不能超过 $L$，点权和不能超过 $S$，求最少需要几条垂直路径才能满足要求。特别地，无解输出 `-1`。 一条垂直路径是一条包含 $v_1, v_2, \cdots, v_k$ 的路径，使得 $v_i(i\ge2)$ 是 $v_{i-1}$ 的父亲。

题目描述

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

输入输出样例

输入样例 #1

3 1 3
1 2 3
1 1

输出样例 #1

3

输入样例 #2

3 3 6
1 2 3
1 1

输出样例 #2

2

输入样例 #3

1 1 10000
10001

输出样例 #3

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

题意翻译

现有 $n$ 个点组成一棵以 $1$ 为根的有根树，第 $i$ 个点的点权为 $w_i$，需将其分成若干条垂直路径使得每一个点当且仅当被一条垂直路径覆盖，同时，每条垂直路径点数不能超过 $L$，点权和不能超过 $S$，求最少需要几条垂直路径才能满足要求。特别地，无解输出 `-1`。 一条垂直路径是一条包含 $v_1, v_2, \cdots, v_k$ 的路径，使得 $v_i(i\ge2)$ 是 $v_{i-1}$ 的父亲。