样例下载

题目描述

有一棵含有 n 个节点的树，节点编号为 0 ~ n-1 。每个节点有一个正整数权值 v[i]。

现在要求把这棵树划分成不超过 k 个部分，每个部分必须是一个连通块，并且任意两个部分之间互不交叠。

定义一个连通块的权值是这个块内所有节点的权值和。

求一种划分方案，使得划分后，权值最大的连通块权值在所有划分方案中是最小的。

输入格式

第一行两个正整数 n，k。输入数据保证 k ≤ n

接下来一行 n 个正整数，第 i 个数 v[i] 表示编号为 i-1 的点的权值。

接下来 n-1 行，每行两个整数 x，y，表示编号为 x 、y 的两个节点之间有条边。输入数据保证 0 ≤ x, y < n

输出格式

一个数，表示在所有的划分方案中，权值最大的连通块的权值的最小值。

样例输入

10 3
10 10 12 15 17 14 16 14 14 18
4 8
6 1
1 2
3 6
5 1
9 3
1 7
0 6
4 6

样例输出

57

数据规模

所有题目输入数据保证符合题目条件，保证有解

30% 的数据，1≤ n ≤ 1000

100% 的数据，1≤ n ≤ 100000, 1 ≤ v[i] ≤ 100000

温馨提示

每个测试点的时间限制: 5秒