← 返回题目列表

AtCoder · past19_k

K. 相邻禁止

中文机器翻译题面 查看原题

问题陈述

有一个 N- 顶点已编号的顶点树 1 通过 N。 的 i第一条边连接顶点 u_i 和顶点 v_i 双向。 顶点 i 有一个整数 A_i 。

判断是否有办法选择 K 之间的顶点 N 使得所选顶点对不相邻。 如果有,求写在所选选项上的最大整数和 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

没有符合要求的选择。