题目描述

小蓝正在一棵含有 $n$ 个结点的树的根结点 $1$ 上，他准备在这棵树上寻宝。结点 $i$ 上有一个物品，价值为 $w_i$ 。然而，小蓝每次寻宝只能从根节点出发走不超过 $k$ 步，每步只能选择走 $1$ 条边或者 $2$ 条边，之后会自动拾取最终停留的结点上的物品并被传送回根结点。请求出小蓝最终能获得的物品的总价值。

输入格式

输入的第一行包含两个正整数 $n, k$ ，用一个空格分隔。

第二行包含 $n$ 个正整数 $w_1, w_2, \cdots, w_n$ ，相邻整数之间使用一个空格分隔。

接下来 $n-1$ 行，每行包含两个正整数 $u_i, v_i$ ，用一个空格分隔，表示结点 $u_i$ 和结点 $v_i$ 之间有一条边。

输出格式

输出一行包含一个整数表示答案。

8 2
6 3 3 1 5 4 3 4
1 2
2 3
2 4
4 5
5 6
6 7
7 8

说明/提示

样例说明

走 $0$ 步能到的结点： $1$ ；
走 $1$ 步能到的结点： $2, 3, 4$ ；
走 $2$ 步能到的结点： $3, 4, 5, 6$ ；

因此能到的结点为： $1, 2, 3, 4, 5, 6$ ，能获得的总价值为 $22$ 。

评测用例规模与约定

对于 $20\%$ 的评测用例， $1 \leq n \leq 15$ ；
对于所有评测用例， $0 \leq k < n \leq 10^5$ ， $1 \leq w_i \leq 10^6$ ， $1 \leq u_i, v_i \leq n$ 。

图与当前步骤

递归现场

题目原文

C++ 代码