Maximum Union Weighted Paths in a Tree

Given a tree with n nodes (numbered 1 through n) where each node i has a positive integer weight w_i, and a positive integer k, select exactly k simple paths from the root (node 1) to some leaves. The value of a solution is defined as the sum of weights of all distinct nodes that occur in at least one of these chosen paths. The objective is to maximize this sum.

More formally, let S be the union of nodes over the chosen k root-to-leaf paths, and let each node u have weight w_u. You are to maximize

Note: A node is considered covered (i.e. included in S) if and only if there exists at least one chosen leaf in its subtree (with respect to the tree rooted at node 1). Since all weights are positive, it is beneficial to cover as many nodes as possible, but the constraint that paths must go from the root to a leaf may prevent covering the entire tree when k is small.

inputFormat

The first line contains two space‐separated integers n and k (1 ≤ n ≤ 10⁵ [note: limits can be adjusted as needed], 1 ≤ k ≤ n).

The second line contains n space‐separated positive integers, where the i^th integer is the weight of node i.

Each of the next n-1 lines contains two integers u and v denoting an edge between nodes u and v. The tree is rooted at node 1.

outputFormat

Output a single integer representing the maximum possible sum of the weights of the nodes in the union of the k chosen root‐to‐leaf paths.

sample

1 1
5

5