CF1249F Maximum Weight Subset

给定一棵包含 $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$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示树中的一条边，连接顶点 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$）。 保证所给的边构成一棵树。

输出一个整数，表示所选子集的最大总权值，且子集中任意两点之间的距离都大于 $k$。

由 ChatGPT 4.1 翻译