问题陈述
有一个 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
没有符合要求的选择。