← 返回题目列表

Codeforces · 1249/F

F. 最大重量子集

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

给你一棵树,它由 $$$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