K - Not Adjacent Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

頂点に 1 から N の番号がついた N 頂点の木があります。 i 番目の辺は頂点 u_i と頂点 v_i を双方向に結んでいます。また、頂点 i には整数 A_i が書かれています。

N 個の頂点から K 個の頂点を選ぶ方法であって、どの選んだ頂点も隣接しないものが存在するか判定してください。存在する場合、選んだ K 個の頂点に書かれた整数の総和の最大値を求めてください。

制約

  • 2\leq N\leq 100
  • 1\leq K \leq N
  • 1\leq u_i,v_i\leq N
  • 1\leq A_i \leq 100
  • 入力されるグラフは木
  • 入力される数値は全て整数

入力

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

N K
u_1 v_1
\vdots
u_{N-1} v_{N-1}
A_1 \ldots A_N

出力

条件を満たす選び方が存在しない場合 -1 を出力せよ。条件を満たす選び方が存在する場合、選んだ K 個の頂点に書かれた整数の総和の最大値を出力せよ。

入力例 1

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

出力例 1

9

頂点 3 と頂点 5 を選ぶのが最適です。

入力例 2

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

出力例 2

34

入力例 3

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

出力例 3

-1

条件を満たす選び方は存在しません。

Problem Statement

There is an N-vertex tree whose vertices are numbered 1 through N. The i-th edge connects vertex u_i and vertex v_i bidirectionally. Vertex i has an integer A_i written on it.

Determine if there is a way to choose K vertices among the N so that no pair of chosen vertices are adjacent. If there is, find the maximum sum of integers written on the chosen K vertices.

Constraints

  • 2\leq N\leq 100
  • 1\leq K \leq N
  • 1\leq u_i,v_i\leq N
  • 1\leq A_i \leq 100
  • The input graph is a tree.
  • All input values are integers.

Input

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

N K
u_1 v_1
\vdots
u_{N-1} v_{N-1}
A_1 \ldots A_N

Output

Print -1 if there is no conforming choice. If there is, print the maximum sum of the integers written on chosen K vertices.

Sample Input 1

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

Sample Output 1

9

It is optimal to choose vertex 3 and vertex 5.

Sample Input 2

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

Sample Output 2

34

Sample Input 3

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

Sample Output 3

-1

There is no conforming choice.