分数: 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