F - Paint Tree 2 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

1 から N までの番号がついた N 頂点からなる木 T と整数 K が与えられます。 i 番目 (1\le i\le N - 1) の辺は頂点 U_i と頂点 V_i を結んでいます。また、頂点 i (1\le i\le N) には整数 A_i が書かれています。はじめ、全ての頂点は白色で塗られています。

あなたは以下の行動を 0 回以上 K 回以下行います：

  • 木 T のパスであってそのパスに含まれるどの頂点も白色で塗られているようなパスを選ぶ。その後、選んだパスに含まれる頂点を全て黒色で塗る。

行動を終えた後に黒色で塗られた頂点に書かれた整数の総和としてあり得る最大値を求めてください。

制約

  • 2\le N\le 2\times 10^5
  • 1\le K\le 5
  • 1\le A_i\le 10^9
  • 1\le U_i < V_i \le N
  • 与えられるグラフは木
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \ldots A_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

答えを出力せよ。

入力例 1

4 1
1 2 4 8
1 2
1 3
1 4

出力例 1

13

頂点 3,4 を両端に持つパスを選ぶと、頂点 1,3,4 を黒く塗ることができます。この場合の黒色で塗られた頂点に書かれた整数の総和は 1+4+8=13 です。

黒色で塗られた頂点に書かれた整数の総和を 13 より大きくすることはできないので、 13 を出力してください。

入力例 2

7 2
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7

出力例 2

27

例えば以下のように操作することで黒色で塗られた頂点に書かれた整数の総和を 27 にすることができます：

  • 頂点 4,5 を両端に持つパスを選ぶ。頂点 2,4,5 を黒く塗る。
  • 頂点 6,7 を両端に持つパスを選ぶ。頂点 3,6,7 を黒く塗る。

黒色で塗られた頂点に書かれた整数の総和を 27 より大きくすることはできないので、 27 を出力してください。

入力例 3

11 3
1 9 1 3 7 9 10 9 7 3 4
7 8
2 7
5 7
3 4
7 11
1 9
1 10
3 6
1 7
3 7

出力例 3

52

Score : 525 points

Problem Statement

You are given a tree T with N vertices numbered from 1 to N, and an integer K. The i-th edge (1\le i\le N - 1) connects vertices U_i and V_i. Also, vertex i (1\le i\le N) has an integer A_i written on it. Initially, all vertices are colored white.

You perform the following action at least 0 times and at most K times:

  • Choose a path in tree T such that all vertices on the path are colored white. Then, color all vertices on the chosen path black.

Find the maximum possible sum of integers written on vertices that are colored black after finishing the actions.

Constraints

  • 2\le N\le 2\times 10^5
  • 1\le K\le 5
  • 1\le A_i\le 10^9
  • 1\le U_i < V_i \le N
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

Output

Output the answer.

Sample Input 1

4 1
1 2 4 8
1 2
1 3
1 4

Sample Output 1

13

If you choose the path with vertices 3 and 4 as endpoints, you can color vertices 1,3,4 black. In this case, the sum of integers written on the colored vertices is 1+4+8=13.

You cannot make the sum of integers written on black vertices greater than 13, so output 13.

Sample Input 2

7 2
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7

Sample Output 2

27

For example, you can make the sum of integers written on black vertices 27 by performing operations as follows:

  • Choose the path with vertices 4 and 5 as endpoints. Color vertices 2,4,5 black.
  • Choose the path with vertices 6 and 7 as endpoints. Color vertices 3,6,7 black.

You cannot make the sum of integers written on black vertices greater than 27, so output 27.

Sample Input 3

11 3
1 9 1 3 7 9 10 9 7 3 4
7 8
2 7
5 7
3 4
7 11
1 9
1 10
3 6
1 7
3 7

Sample Output 3

52