[ARC096D] Sweet Alchemy

题意翻译

有 $n$ 个物品和 $x$ 个特殊材料,制作第 $i$ 个物品需要 $m_i$ 个特殊材料。给出一个整数 $d$,对于每个 $i\ \ (2\le i\le n)$ 给定 $p_i\ \ (1\le p_i<i)$,设在材料充足的情况下制作第 $i$ 个物品的个数为 $c_i$,需满足 $c_{p_i}\le c_i \le c_{p_i}+d$ 。最大化制作的物品数。 输入格式: 第一行有三个整数:$n,x,d$ 。 接下来一行有一个整数表示 $m_1$。 最后 $n-1$ 行每行有两个整数,分别表示 $m_i$ 和 $p_i$ 。 输出格式: 仅输出一行,表示在满足条件的情况下可以制作的最多物品数。 数据范围: $1\le n \le 50,\ 1\le x,m_i\le 10^9,\ 0\le d \le 10^9, 1\le p_i < i$

题目描述

[problemUrl]: https://arc096.contest.atcoder.jp/tasks/arc096_d パティシエの赤木さんは、「お菓子の素」という粉のみを材料として $ N $ 種類のドーナツを作ることができます。これらのドーナツはドーナツ $ 1 $ 、ドーナツ $ 2 $ 、 $ ... $ 、ドーナツ $ N $ と呼ばれます。ドーナツ $ i $ $ (1\ <\ =\ i\ <\ =\ N) $ を $ 1 $ 個作るには、お菓子の素 $ m_i $ グラムを消費する必要があります。なお、 $ 0.5 $ 個など整数でない個数のドーナツを作ることはできません。 これらのドーナツのレシピは、ドーナツ $ 1 $ のレシピから改変を繰り返して開発されたものです。 具体的には、ドーナツ $ i $ $ (2\ <\ =\ i\ <\ =\ N) $ のレシピはドーナツ $ p_i $ $ (1\ <\ =\ p_i\ <\ i) $ のレシピを直接改変したものです。 いま、赤木さんはお菓子の素を $ X $ グラム持っています。これを使って、今夜のパーティーに向けて可能な限りたくさんのドーナツを作ることにしました。ただし、来客の好みは様々なので、次の条件を守ることにしました。 - ドーナツ $ i $ $ (1\ <\ =\ i\ <\ =\ N) $ を作る個数を $ c_i $ とする。 $ 2\ <\ =\ i\ <\ =\ N $ であるようなどの整数 $ i $ に対しても、 $ c_{p_i}\ <\ =\ c_i\ <\ =\ c_{p_i}\ +\ D $ となるように作る。ここで、 $ D $ はあらかじめ決まった値である。 このとき、最大で何個のドーナツを作ることができるでしょうか?お菓子の素を使い切る必要はありません。 Akaki, a patissier, can make $ N $ kinds of doughnut using only a certain powder called "Okashi no Moto" (literally "material of pastry", simply called Moto below) as ingredient. These doughnuts are called Doughnut $ 1 $ , Doughnut $ 2 $ , $ ..., $ Doughnut $ N $ . In order to make one Doughnut $ i $ $ (1\ <\ =\ i\ <\ =\ N) $ , she needs to consume $ m_i $ grams of Moto. She cannot make a non-integer number of doughnuts, such as $ 0.5 $ doughnuts. The recipes of these doughnuts are developed by repeated modifications from the recipe of Doughnut $ 1 $ . Specifically, the recipe of Doughnut $ i $ $ (2\ <\ =\ i\ <\ =\ N) $ is a direct modification of the recipe of Doughnut $ p_i $ $ (1\ <\ =\ p_i\ <\ i) $ . Now, she has $ X $ grams of Moto. She decides to make as many doughnuts as possible for a party tonight. However, since the tastes of the guests differ, she will obey the following condition: - Let $ c_i $ be the number of Doughnut $ i $ $ (1\ <\ =\ i\ <\ =\ N) $ that she makes. For each integer $ i $ such that $ 2\ <\ =\ i\ <\ =\ N $ , $ c_{p_i}\ <\ =\ c_i\ <\ =\ c_{p_i}\ +\ D $ must hold. Here, $ D $ is a predetermined value. At most how many doughnuts can be made here? She does not necessarily need to consume all of her Moto.

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ X $ $ D $ $ m_1 $ $ m_2 $ $ p_2 $ $ : $ $ m_N $ $ p_N $ ```

输出格式


Print the maximum number of doughnuts that can be made under the condition.

输入输出样例

输入样例 #1

3 100 1
15
10 1
20 1

输出样例 #1

7

输入样例 #2

3 100 10
15
10 1
20 1

输出样例 #2

10

输入样例 #3

5 1000000000 1000000
123
159 1
111 1
135 3
147 3

输出样例 #3

7496296

输入样例 #4

3 100 1
15
10 1
20 1

输出样例 #4

7

输入样例 #5

3 100 10
15
10 1
20 1

输出样例 #5

10

输入样例 #6

5 1000000000 1000000
123
159 1
111 1
135 3
147 3

输出样例 #6

7496296

说明

### 制約 - $ 2\ <\ =\ N\ <\ =\ 50 $ - $ 1\ <\ =\ X\ <\ =\ 10^9 $ - $ 0\ <\ =\ D\ <\ =\ 10^9 $ - $ 1\ <\ =\ m_i\ <\ =\ 10^9 $ $ (1\ <\ =\ i\ <\ =\ N) $ - $ 1\ <\ =\ p_i\ <\ i $ $ (2\ <\ =\ i\ <\ =\ N) $ - 入力中の値はすべて整数である。 ### Constraints - $ 2\ <\ =\ N\ <\ =\ 50 $ - $ 1\ <\ =\ X\ <\ =\ 10^9 $ - $ 0\ <\ =\ D\ <\ =\ 10^9 $ - $ 1\ <\ =\ m_i\ <\ =\ 10^9 $ $ (1\ <\ =\ i\ <\ =\ N) $ - $ 1\ <\ =\ p_i\ <\ i $ $ (2\ <\ =\ i\ <\ =\ N) $ - All values in input are integers. ### Sample Explanation 1 $ 100 $ グラムのお菓子の素があり、赤木さんは $ 3 $ 種類のドーナツを作ることができ、守るべき条件は $ c_1\ <\ =\ c_2\ <\ =\ c_1\ +\ 1 $ 、 $ c_1\ <\ =\ c_3\ <\ =\ c_1\ +\ 1 $ です。ドーナツ $ 1 $ を $ 2 $ 個、ドーナツ $ 2 $ を $ 3 $ 個、ドーナツ $ 3 $ を $ 2 $ 個作るのが最適です。 ### Sample Explanation 2 入力例 1 からお菓子の素の量やドーナツのレシピそのものは変わっていませんが、最後の条件が緩くなっています。この場合、ドーナツ $ 2 $ だけを $ 10 $ 個作るのが最適です。このように、必ずしもすべての種類のドーナツを作らなくても構いません。 ### Sample Explanation 4 She has $ 100 $ grams of Moto, can make three kinds of doughnuts, and the conditions that must hold are $ c_1\ <\ =\ c_2\ <\ =\ c_1\ +\ 1 $ and $ c_1\ <\ =\ c_3\ <\ =\ c_1\ +\ 1 $ . It is optimal to make two Doughnuts $ 1 $ , three Doughnuts $ 2 $ and two Doughnuts $ 3 $ . ### Sample Explanation 5 The amount of Moto and the recipes of the doughnuts are not changed from Sample Input 1, but the last conditions are relaxed. In this case, it is optimal to make just ten Doughnuts $ 2 $ . As seen here, she does not necessarily need to make all kinds of doughnuts.