E - 通信ネットワークの妨害 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

N 個の基地局からなる通信ネットワークがあります。基地局は 1 から N まで番号が付けられています。これらの基地局は N - 1 本の通信回線で結ばれており、どの基地局からどの基地局へも回線を辿って通信できます（つまり木構造をなしています）。i 番目の回線（1 \leq i \leq N-1）は基地局 A_i と基地局 B_i を双方向に結んでいます。また、基地局 j（1 \leq j \leq N）にはデータ量 V_j のデータが保管されています。

このネットワークにおいて、攻撃者の高橋君と管理者の青木君が以下の手順でゲームを行います。

  1. 青木君の行動： N - 1 本の回線のうち 1 本を選んで 遮断 するか、あるいは 1 本も遮断しないかを決定します。遮断された回線は使用不能になります。遮断できる回線は 高々 1 本 です。
  2. 高橋君の行動： 青木君がどの回線を遮断したか（あるいは遮断しなかったか）をすべて知った上で、N 個の基地局の中から侵入先を 1 つ選びます。遮断によってネットワークが分断されていても、高橋君は任意の基地局を侵入先として選ぶことができます。
  3. 結果： 高橋君は、侵入先の基地局から 使用可能な（遮断されていない）回線のみ を辿って距離 D 以下で到達できるすべての基地局のデータを盗み出します。侵入先の基地局自身からも必ずデータを盗み出します。

ここで、2 つの基地局間の 距離 とは、使用可能な回線のみを辿って一方から他方へ到達するために経由する回線の本数の最小値として定義します。使用可能な回線のみでは到達できない場合、距離は \infty とみなします。特に、侵入先の基地局自身への距離は 0 です。

高橋君は盗み出すデータの合計量を 最大化 するように行動し、青木君はそれを 最小化 するように行動します。両者がともに最適に行動したとき、高橋君が盗み出せるデータの合計量を求めてください。

制約

  • 2 \leq N \leq 3000
  • 1 \leq D \leq N - 1
  • 1 \leq V_i \leq 10^9（1 \leq i \leq N）
  • 1 \leq A_i, B_i \leq N（1 \leq i \leq N - 1）
  • 入力で与えられるグラフは木である
  • 入力はすべて整数である

入力

N D
V_1 V_2 \ldots V_N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
  • 1 行目には、基地局の数 N と侵入範囲を表す整数 D が、スペース区切りで与えられる。
  • 2 行目には、各基地局のデータ量 V_1, V_2, \ldots, V_N がスペース区切りで与えられる。
  • 続く N - 1 行のうち i 行目（1 \leq i \leq N - 1）には、i 番目の回線が結ぶ 2 つの基地局の番号 A_i と B_i がスペース区切りで与えられる。

出力

両者が最適に行動したとき、高橋君が盗み出せるデータの合計量を 1 行に出力してください。

入力例 1

4 1
3 10 2 5
1 2
2 3
2 4

出力例 1

15

入力例 2

5 2
1 100 1 100 1
1 2
1 3
3 4
3 5

出力例 2

102

入力例 3

12 2
8 6 15 3 10 7 20 1 9 4 12 5
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 10
7 11
11 12

出力例 3

52

入力例 4

25 4
17 23 5 100 8 42 11 6 29 31 7 13 19 2 53 47 3 37 41 59 61 67 71 73 79
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
9 17
10 18
11 19
12 20
13 21
14 22
15 23
20 24
20 25

出力例 4

555

入力例 5

2 1
1000000000 1
1 2

出力例 5

1000000000

Score : 433 pts

Problem Statement

There is a communication network consisting of N base stations. The base stations are numbered from 1 to N. These base stations are connected by N - 1 communication lines, and any base station can communicate with any other base station by traversing the lines (that is, they form a tree structure). The i-th line (1 \leq i \leq N-1) bidirectionally connects base station A_i and base station B_i. Also, base station j (1 \leq j \leq N) stores data of volume V_j.

In this network, Takahashi (the attacker) and Aoki (the administrator) play a game according to the following procedure:

  1. Aoki's Action: Aoki chooses to disconnect one of the N - 1 lines, or decides not to disconnect any lines. Disconnected lines become unusable. Aoki can disconnect at most one line.
  2. Takahashi's Action: Knowing exactly which line Aoki disconnected (or that he did not disconnect any), Takahashi chooses one base station from the N base stations as the target of his intrusion. Even if the network is disconnected, Takahashi can choose any base station as the target.
  3. Result: Takahashi steals data from all base stations that can be reached from the target base station within a distance of D or less, using only the usable (not disconnected) lines. He always steals data from the target base station itself.

Here, the distance between two base stations is defined as the minimum number of lines traversed to reach one from the other using only usable lines. If they cannot reach each other using only usable lines, the distance is considered to be \infty. In particular, the distance from the target base station to itself is 0.

Takahashi acts to maximize the total volume of data stolen, and Aoki acts to minimize it. Find the total volume of data Takahashi can steal when both players play optimally.

Constraints

  • 2 \leq N \leq 3000
  • 1 \leq D \leq N - 1
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq A_i, B_i \leq N (1 \leq i \leq N - 1)
  • The graph given in the input is a tree.
  • All input values are integers.

Input

N D
V_1 V_2 \ldots V_N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
  • The first line contains the number of base stations N and the integer D representing the intrusion range, separated by a space.
  • The second line contains the data volumes of the base stations V_1, V_2, \ldots, V_N, separated by spaces.
  • In the following N - 1 lines, the i-th line (1 \leq i \leq N - 1) contains the numbers of the two base stations A_i and B_i connected by the i-th communication line, separated by a space.

Output

Print the total volume of data Takahashi can steal when both players play optimally in a single line.

Sample Input 1

4 1
3 10 2 5
1 2
2 3
2 4

Sample Output 1

15

Sample Input 2

5 2
1 100 1 100 1
1 2
1 3
3 4
3 5

Sample Output 2

102

Sample Input 3

12 2
8 6 15 3 10 7 20 1 9 4 12 5
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
7 10
7 11
11 12

Sample Output 3

52

Sample Input 4

25 4
17 23 5 100 8 42 11 6 29 31 7 13 19 2 53 47 3 37 41 59 61 67 71 73 79
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
9 17
10 18
11 19
12 20
13 21
14 22
15 23
20 24
20 25

Sample Output 4

555

Sample Input 5

2 1
1000000000 1
1 2

Sample Output 5

1000000000