题面翻译
题目描述 自从Krešo开始种植辣椒以来，克罗地亚各地的N家餐馆都对他的辣椒感兴趣，因此他们可以用真正的香料来丰富他们的菜肴。由于需求量很大，Krešo决定开始作为辣椒的送货员。 餐馆用从1到N的数字表示，并且与N-1个道路相互连接，使得可以在任何两个餐馆之间旅行。Krešo在1号餐厅开始他的旅程。在一个单位的时间里，他可以开车到相邻的餐厅或将辣椒送到现在的餐馆。对于每家餐厅，我们都知道所需的辣椒数量Ai 由于交付货物很累，Krešo决定在交付和旅行上花费总共M个单位的时间，之后他计划休息一下。 确定Krešo在给定时间范围内可以提供的最大辣椒数量。你可以假设Krešo总是带有无限量的辣椒。 输入输出格式 输入格式： 第一行输入包含两个整数N和M（1≤N，M≤500），餐馆数量和Krešo计划用于交付辣椒的时间。 第二行输入包含N个整数 Ai （1≤ Ai ≤ 10 ^ 6 ），用i表示的餐馆所需的辣椒数量（1≤i≤N）。 以下N-1行中的每一行包含两个整数U和V（1≤U，V≤N，U≠V），其表示餐馆U和V之间的道路。 输出格式： 您必须输出Krešo在给定时间范围内可以提供的最大量的辣椒。
题目描述
Ever since Krešo started growing chili peppers, N restaurants all over Croatia showed interest in his peppers so they could enrich their dishes with real spice. Because of high demand, Krešo decided to start working as a delivery guy of chili peppers.
The restaurants are denoted with numbers from 1 to N and are mutually connected with N - 1 roads such that traveling between any two restaurants is possible. Krešo begins his journey in the restaurant denoted with 1. In one unit of time, he can either drive to the adjacent restaurant or deliver the peppers to the current restaurant. For each restaurant, we know the required amount of peppers $A_i$.
Since delivering goods is tiring, Krešo decided to spend a total of M units of time on delivery and travel, after which he plans to take a break.
Determine the maximal amount of peppers Krešo can deliver in the given timeframe. You can assume that Krešo always carries an unlimited supply of peppers.
输入格式
The first line of input contains two integers N and M (1 ≤ N, M ≤ 500), the number of restaurants and the time Krešo plans to spend delivering peppers.
The second line of input contains N integers $A_i$ (1 ≤ $A_i$ ≤ $10^6$ ), the required amount of peppers for restaurants denoted with i (1 ≤ i ≤ N).
Each of the following N - 1 lines contains two integers U and V (1 ≤ U, V ≤ N, U ≠ V) that represent the road between restaurants U and V.
输出格式
You must output the maximal amount of peppers Krešo can deliver in the given timeframe.
样例 #1
样例输入 #1
3 5
9 2 5
1 2
1 3样例输出 #1
14样例 #2
样例输入 #2
4 5
1 1 1 2
1 2
2 3
3 4样例输出 #2
3样例 #3
样例输入 #3
5 10
1 3 5 2 4
5 2
3 1
2 3
4 2样例输出 #3
15提示
Clarification of the first test case:
第一步，Krešo 会将辣椒送到餐厅 1。
第二步，Krešo 将前往餐厅 3。
第三步，Krešo 将辣椒送到餐厅 3。
他剩下 2 个单位的时间，他可以开车去餐厅 2，但他没有 1 个单位的时间去餐厅 2。 把辣椒送到那家餐馆。