← 返回题目列表

AtCoder · abc416_f

F. 油漆树 2

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

分数: 525 点

问题陈述

你得到一棵树 T 与 N 顶点编号自 1 to N,和一个整数 K。的 i第边缘 (1\le i\le N - 1) 连接顶点 U_i 和 V_i。另外,顶点 上面写着 i (1\le i\le N) 有一个整数 上面写着 A_i 。最初,所有顶点都是白色的。

您至少执行以下操作 0 次且最多 K 次:

  • 选择树中的路径 T 使得路径上的所有顶点都变成白色。然后,将所选路径上的所有顶点着色为黑色。

求完成动作后写在黑色顶点上的整数的最大可能和。

约束

  • 2\le N\le 2\times 10^5
  • 1\le K\le 5
  • 1\le A_i\le 10^9
  • 1\le U_i < V_i \le N
  • 给定的图是一棵树。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \ldots A_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

输出

输出答案。


示例输入 1

4 1
1 2 4 8
1 2
1 3
1 4

示例输出 1

13

如果选择有顶点的路径 3 和 4 作为端点,您可以为顶点着色 1,3,4 黑色。在这种情况下,写在彩色顶点上的整数之和是 1+4+8=13.

不能使写在黑色顶点上的整数之和大于 13,所以输出 13.


示例输入 2

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

示例输出 2

27

例如,可以将写在黑色顶点上的整数相加 27 通过执行如下操作:

  • 选择带有顶点的路径 4 和 5 作为端点。颜色顶点 2,4,5 黑色。
  • 选择带有顶点的路径 6 和 7 作为端点。颜色顶点 3,6,7 黑色。

不能使写在黑色顶点上的整数之和大于 27,所以输出 27.


示例输入 3

11 3
1 9 1 3 7 9 10 9 7 3 4
7 8
2 7
5 7
3 4
7 11
1 9
1 10
3 6
1 7
3 7

示例输出 3

52