给你一棵树,它由 $$$n$$$ 个顶点组成。回想一下,树是一个没有循环的连通无向图。
树的示例。
顶点编号从 $$$1$$$ 到 $$$n$$$。所有顶点都有权重,顶点$$$v$$$的权重为$$$a_v$$$。
回想一下,树中两个顶点之间的距离是它们之间的简单路径上的边数。
你的任务是找到总权重最大的顶点子集(该子集的权重是其中所有顶点的权重之和),使得该子集中不存在距离为 $$$k$$$ 或更小的顶点对。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 200$$$) — 分别是树中的顶点数和距离限制。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$),其中 $$$a_i$$$ 是顶点 $$$i$$$ 的权重。
接下来的 $$$n - 1$$$ 行包含树的边缘。边 $$$i$$$ 由两个整数 $$$u_i$$$ 和 $$$v_i$$$ 表示 - 它连接的顶点的标签($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$)。
保证给定的边形成一棵树。
输出
打印一个整数 — 所有顶点对的距离都大于 $$$k$$$ 的子集的最大总权重。
示例
输入 #1
5 1 1 2 3 4 5 1 2 2 3 3 4 3 5
输出 #1
11
输入 #2
7 2 2 1 2 1 2 1 1 6 4 1 5 3 1 2 3 7 5 7 4
输出 #2
4