时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
You have a tree with N nodes and N-1 edges. Each node has a weight. The i-th node's weight is Wi.
Now you should divide the N nodes into K connected parts . Each part has at least one node.
The sum of all node's Wi in a part is X. The minimum X of all parts is Y. You need to calculate maximum Y.
Now you should divide the N nodes into K connected parts . Each part has at least one node.
The sum of all node's Wi in a part is X. The minimum X of all parts is Y. You need to calculate maximum Y.
输入描述:
The first line contains two integers N and K.
Each of the following N-1 lines contain two integers x,y denoting there is an edge between x and y.
The next line N integers W1,W2,...WN.
输出描述:
Print one integer -- the maximized Y.