Maximizing the Chase–Fugitive Iron Ball Difference

In a maze modeled as a tree with \(n\) nodes (rooms) and \(n-1\) bidirectional corridors, each room \(i\) initially contains \(F_i\) iron balls. When the fugitive passes through a room he is hindered by the iron balls originally in that room. The fugitive chooses a simple path (i.e. a path that does not repeat any corridor) to enter and exit the maze. He also has \(V\) magnets. Upon entering a room, before leaving the room he can choose to drop one magnet. When he leaves the room, after his departure, the magnet immediately attracts all iron balls from every room adjacent to it (neighbors in the maze). Note that the fugitive suffers only the original iron balls present in the room when he enters—even if extra iron balls later migrate into that room due to an adjacent magnet.

After the fugitive leaves, a chaser traverses exactly the same path. However, the chaser will encounter all of the iron balls present in the rooms along the path after any magnet effects have taken place. In particular, if a magnet is dropped in room \(i\), then for every room \(j\) adjacent to \(i\) that also lies on the fugitive's path, the iron balls \(F_j\) originally in room \(j\) are relocated to room \(i\) and will be encountered by the chaser when he visits room \(i\). (If an adjacent room happens to be affected by more than one magnet along the path, its iron balls will be counted each time.)

The fugitive wants to choose both a path and a selection of at most \(V\) rooms (where he will drop a magnet) in order to maximize the difference:

[ \text{Difference} = \text{(total iron balls encountered by the chaser)} - \text{(total iron balls obstructing the fugitive)}. ]

Since the fugitive always gets obstructed by the original iron balls in every room he passes, his cost is \(\sum_{i\in \text{path}} F_i\). If no magnets are used, the chaser too encounters \(\sum_{i\in \text{path}} F_i\) and the difference is 0. However, whenever the fugitive drops a magnet in a room \(i\), for every room \(j\) that is adjacent to \(i\) and is also on the chosen path, an extra \(F_j\) iron balls are relocated to room \(i\) (even if room \(j\) is later also used for a magnet). Consequently, the chaser's total becomes

[ \sum_{i \in \text{path}} F_i + \sum_{i \in S} \sum_{\substack{j \in \text{path} \ j \text{ is adjacent to } i}} F_j, ]

and the difference is exactly

[ \sum_{i \in S} \sum_{\substack{j \in \text{path} \ j \text{ is adjacent to } i}} F_j. ]

Your task is to help the fugitive pick a simple path in the tree and choose at most \(V\) rooms (vertices on that path) where he drops a magnet so as to maximize the above difference. Note that if both endpoints of a corridor have a magnet dropped, then the corresponding iron balls are counted for each magnet (i.e. counted twice).

Input Format: The first line contains two integers \(n\) and \(V\). The second line contains \(n\) integers \(F_1, F_2, \dots, F_n\). Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) indicating a corridor between rooms \(u\) and \(v\). It is guaranteed that the maze is a tree, i.e. the graph is connected and has no cycles.

Output Format: Output a single integer, the maximum possible difference between the number of iron balls encountered by the chaser and the number encountered by the fugitive.

inputFormat

The first line contains two integers \(n\) and \(V\) (the number of rooms and the number of magnets available). The second line contains \(n\) integers \(F_1, F_2, \dots, F_n\) representing the number of iron balls in each room. The following \(n-1\) lines each contain two integers \(u\) and \(v\) indicating that there is a corridor connecting room \(u\) and room \(v\).

outputFormat

Output a single integer which is the maximum difference (chaser's encountered iron balls minus fugitive's encountered iron balls) achievable by an optimal choice of path and magnet drop decisions.

sample

2 1
3 5
1 2

5