← 返回题目列表

Codeforces · 1059/E

E. 分裂树

中文机器翻译题面 查看原题

给你一棵在 $$$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

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

注意

在第一个示例中,树被分为 $$$\{1\}、\ \{2\}、\ \{3\}$$$。

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

在第三个示例中,不可能拆分树。