1711 . Apple Tree
TopCoder
Tags
Description
你是一顆Orange。在厭倦了和 Pear的相處之後，你來到了一個神秘的地方。
你仔細一看，原來你在一顆 Apple Tree的樹根上。
而且你驚喜地發現，這顆樹的每個節點上都有很多好吃的點點(Tic-Tac)。
每當你走到一個節點上，你就可以把上面的所有點點吃掉。當然，每個點點只能吃一次。
但是自然你不能肆無忌憚地吃點點，你發現你的腳被綁在殺人裝置上，你只要走超過$k$ 步
你的下場就會和棉花糖(Marshmallow)一樣保不住自己的腎。所謂走一步是指從一個節點走到
任一與他相鄰的節點。
現在你想知道，在你想要保有你的腎的前提下，你最多能吃多少點點？
(你一開始在節點$1$，且你知道這棵Apple Tree上任兩節點間皆恰好有一條簡單路徑。)
Input Format
對於 $20\%$ 的測試資料，$n \leq 10$
對於 $60\%$ 的測試資料，$n \leq 200$
對於$100\%$ 的測試資料，$n \leq 1,000$
輸入第一行包含兩個數字$n$、$k$，表示 Apple Tree 有$n$個節點(編號$1$~$n$ )、你不能走超過$k$ 步。
接下來一行有$n$個數字，第$i$個數字$t_i$表示節點$i$上面有$t_i$個點點，$0 \leq t_i \leq 1,000$。
接下來有$n-1$ 行，每行兩個數字$a , b$，表示樹有一條邊是連結$a$ $b$ 和 。$1 \leq a , b \leq n$。
Output Format
輸出只有一個數字$c$，表示能吃到的點點數量的最大值。
Sample Input 1
2 1
0 11
1 2
0 11
1 2
Sample Output 1
11
Hints
Problem Source
原TIOJ1711 / 建國中學99年校內培訓contest #9 prob 4
source:POJ Monthly
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |