TopCoder

Caido
Waimai

User's AC Ratio

75.8% (25/33)

Submission's AC Ratio

20.5% (52/254)

Tags

Description

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

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

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

Input Format

對於 20% 的測試資料,n10
對於 60% 的測試資料,n200
對於100% 的測試資料,n1,000

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

Output Format

輸出只有一個數字c,表示能吃到的點點數量的最大值。

Sample Input 1

2 1
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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