TopCoder

Thumb output jddoia
$\huge 南ことり$
不要再虐我了$ε=ε=ε=ε=ε=ε=┌(; ̄◇ ̄)┘$

User's AC Ratio

33.3% (2/6)

Submission's AC Ratio

8.2% (4/49)

Description

你是一顆Orange。在厭倦了和 Pear的相處之後,你來到了一個神秘的地方。
你仔細一看,原來你在一顆 Apple Tree的樹根上。
而且你驚喜地發現,這顆樹的每個節點上都有很多好吃的點點(Tic-Tac)。
每當你走到一個節點上,你就可以把上面的所有點點吃掉。當然,每個點點只能吃一次。

但是自然你不能肆無忌憚地吃點點,你發現你的腳被綁在殺人裝置上,你只要走超過k 步
你的下場就會和棉花糖(Marshmallow)一樣保不住自己的腎。所謂走一步是指從一個節點走到
任一與他相鄰的節點。

現在你想知道,在你想要保有你的腎的前提下,你最多能吃多少點點?
(你一開始在節點1,且你知道這棵Apple Tree上任兩節點間皆恰好有一條簡單路徑。)

Input Format

對於 20% 的測試資料,n ≤ 10
對於 60% 的測試資料,n ≤ 200
對於100% 的測試資料,n ≤ 1,000

輸入第一行包含兩個數字n , k,表示 Apple Tree n 有 個節點(編號1~n )、你不能走超過k 步。
接下來一行有n 個數字,第 i個數字ti 表示節點i 上面有ti 個點點,0 ≤ ti ≤ 1,000。
接下來有n-1 行,每行兩個數字a , b,表示樹有一條邊是連結a b 和 。1 ≤ a , b ≤ 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