三口羊現在經營著一間商店，裡面有 $N$ 樣商品，在這間商店中有著許多不同的優惠，他想知道在客人有 $M$ 元時且購買到的商品不重複時最多可以獲得價值為多少的商品。
具體而言，商品優惠如下:
這些商品彼此之間會形成一顆有向森林(沒有環)，對於第 $i$ 個商品，消費者可以花費 $c_i$ 元將第 $i$ 樣商品買下來，同時 $c_i$ 也代表了第 $i$ 樣物品的價值，也可以花費 $d_i$ 元將以第 $i$ 樣物品為root的子樹下的商品通通買走。
第一行有兩個整數$N,M$ 代表意義如題序所敘述
第二行有 $N$ 個整數 $f_i (0 \le i < N)$ 第 $i$ 樣物品的父節點(若為 -1 代表該樣物品沒有父節點)
接下來有 $N$ 行，每行有 $2$ 個整數 $c_i$,$d_i$ 代表意義如題序所敘述
$1\le N,M\le 1000$
$-1 \le f_i < i$
$1\le ci,di \le 1000$
請輸出一個整數，代表顧客在有 $M$ 塊錢時可以購買最大的商品總價值是多少
1 1 -1 1 1
1
10 10 -1 0 0 0 1 3 -1 -1 6 4 6 7 3 8 2 3 5 105 3 9 2 3 2 7 1 8 77 3 2 9
100
範例 2 說明
畫完樹狀圖後,可發現:
把以 0 為樹根的子樹買下來,
(以 7 塊錢買下總價值 23 的物品,被買下來的物品編號分別為 0、1、2、3、4、5、9)
再把以 8 為樹根的子樹買下來,
(以 3 塊錢買下總價值 77 的物品,被買下來的物品編號只有 8,因為 8 沒有子節點)
(註:只要錢足夠,用 77 元買下 8 號物品也可以的,但明顯地不符合求最佳解的策略)
以此方法購物,可以用 7+3=10 元買到總價值 23+77=100 的物品,
並且你會發現沒有其他買法可以買到更高總價值的物品。
subtask 1 20% : $N\le 15$
subtask 2 30% : 對於所有的$f_i$皆滿足$f_i=-1$
subtask 3 50% : other
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||