TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

68.0% (17/25)

Submission's AC Ratio

19.6% (40/204)

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

2 1
0 11
1 2

Sample Output

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10