#P12343. [蓝桥杯 2025 省 AB/Python B 第二场] 树上寻宝

[蓝桥杯 2025 省 AB/Python B 第二场] 树上寻宝

题目描述

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

输入格式

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

第二行包含 nn 个正整数 w1,w2,,wnw_1, w_2, \cdots, w_n,相邻整数之间使用一个空格分隔。

接下来 n1n-1 行,每行包含两个正整数 ui,viu_i, v_i,用一个空格分隔,表示结点 uiu_i 和结点 viv_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
22

提示

样例说明

  • 00 步能到的结点:11
  • 11 步能到的结点:2,3,42, 3, 4
  • 22 步能到的结点:3,4,5,63, 4, 5, 6

因此能到的结点为:1,2,3,4,5,61, 2, 3, 4, 5, 6,能获得的总价值为 2222

评测用例规模与约定

  • 对于 20%20\% 的评测用例,1n151 \leq n \leq 15
  • 对于所有评测用例,0k<n1050 \leq k < n \leq 10^51wi1061 \leq w_i \leq 10^61ui,vin1 \leq u_i, v_i \leq n