CF1249F.Maximum Weight Subset

You are given a tree, which consists of $n$ vertices. Recall that a tree is a connected undirected graph without cycles.

Example of a tree.

Vertices are numbered from $1$ to $n$. All vertices have weights, the weight of the vertex $v$ is $a_v$.

Recall that the distance between two vertices in the tree is the number of edges on a simple path between them.

Your task is to find the subset of vertices with the maximum total weight (the weight of the subset is the sum of weights of all vertices in it) such that there is no pair of vertices with the distance $k$ or less between them in this subset.

给你一棵包含 $n$ 个顶点的树。注意：树是一种无环的连通无向图。

树的一个示例。

顶点编号为 $1$ 到 $n$。每个顶点均具有一个权值，顶点 $v$ 的权值为 $a_v$。

注意：树中两个顶点之间的距离定义为它们之间简单路径上的边数。

你的任务是找出一个顶点子集，使得该子集的总权值（即子集中所有顶点权值之和）最大，且子集中任意两个顶点之间的距离均严格大于 $k$。

The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 200$) — the number of vertices in the tree and the distance restriction, respectively.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$), where $a_i$ is the weight of the vertex $i$.

The next $n - 1$ lines contain edges of the tree. Edge $i$ is denoted by two integers $u_i$ and $v_i$ — the labels of vertices it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$).

It is guaranteed that the given edges form a tree.

输入的第一行包含两个整数 $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$）。

保证所给的边构成一棵树。

Print one integer — the maximum total weight of the subset in which all pairs of vertices have distance more than $k$.

输出一个整数——满足其中任意两个顶点间距离均大于 $k$ 的子集的最大总权重。