AT_past19_k 隣接禁止

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，且为无向边。在顶点 $i$ 上写有整数 $A_i$。 请判断是否存在一种方法，从这 $N$ 个顶点中选择 $K$ 个顶点，使得选出的任意两个顶点都不是相邻的。如果存在，请求出所选 $K$ 个顶点上的整数之和的最大值。

输入从标准输入读入，格式如下： > $N$ $K$ $u_1$ $v_1$ ⋮ $u_{N-1}$ $v_{N-1}$ $A_1$ $A_2$ ⋯ $A_N$

如果不存在满足条件的选法，输出 $-1$。如果存在，输出所选 $K$ 个顶点上整数之和的最大值。

### 样例解释 1 最优的做法是选择顶点 $3$ 和顶点 $5$。 ### 样例解释 3 不存在满足条件的选法。 ### 数据范围 - $2\leq N\leq 100$ - $1\leq K \leq N$ - $1\leq u_i,v_i\leq N$ - $1\leq A_i \leq 100$ - 输入的图是一棵树。 - 所有输入数值均为整数。 由 ChatGPT 5 翻译