Treasure Hunt on a Tree

Little Blue is at the root (node 1) of a tree with \(n\) nodes. Each node \(i\) contains an item of value \(w_i\). He embarks on treasure hunts on this tree. For each hunt, he starts at the root and takes at most \(k\) moves. In each move, he can traverse exactly 1 edge or exactly 2 consecutive edges, i.e. he can either move to an adjacent node or jump over one node along the unique simple path.

After completing his moves, he collects the item at the final node and is teleported back to the root. Each item can be collected at most once. Note that the minimum number of moves required to reach a node at distance \(d\) is given by \(\lceil d/2 \rceil\). Therefore, a node is reachable if and only if \[ \lceil d/2 \rceil \le k, \] which is equivalent to \(d \le 2k\).

Determine the maximum total value of the items that Little Blue can collect.

inputFormat

The input consists of several lines:

• The first line contains two integers \(n\) and \(k\): the number of nodes in the tree and the maximum number of moves allowed per treasure hunt.
• The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\) where \(w_i\) represents the value of the item at node \(i\).
• Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), representing an undirected edge between nodes \(u\) and \(v\).

It is guaranteed that the edges form a tree with root at node 1.

outputFormat

Output a single integer: the maximum total value Little Blue can collect by picking reachable nodes (i.e. nodes whose distance from the root is at most \(2k\)).

sample

5 1
1 2 3 4 5
1 2
1 3
2 4
3 5

15