Minimizing Adjacent Weight Differences on a Tree

You are given a tree with n nodes and m leaf nodes. The m leaf nodes are numbered from 1 to m and each leaf i has an assigned weight (r_i). The remaining (n-m\nodes (internal nodes) do not have weights, and you are allowed to assign them arbitrary real values. Your task is to assign weights to all internal nodes so that the sum of absolute differences on every edge is minimized.

Formally, let every node (i) have an assigned value (x_i) (for leaf nodes (x_i = r_i) is fixed). The objective is to minimize [ \sum_{(u,v) \in E} |x_u - x_v|, ] where (E) is the set of edges of the tree.

A key observation is that, because you can choose the values for free (internal) nodes arbitrarily, for any edge bridging two parts of the tree that contain at least one fixed leaf each, the minimum cost contributed by that edge is the minimum possible difference enforced by the fixed weights. In other words, if an edge splits the tree into two parts with fixed weights whose ranges overlap, the edge cost can be zero; otherwise, it is the gap between the two ranges.

A standard approach to solve this problem is to perform a tree dynamic programming (DP) from an arbitrary root (choose a fixed leaf if available) that uses a merge operation on sorted lists of fixed weights (from subtrees) and then computes the extra cost required when enforcing a common assignment at the parent. For a sorted multiset S the function [ f(x)=\sum_{w\in S}|w-x| ] is convex and its minimum is attained when (x) is a median of S.

You are required to compute and output the minimized total cost.

inputFormat

The input is given as follows (read from standard input):

The first line contains two integers n and m where 1 (\leq m \leq n).

The second line contains m integers: (r_1, r_2, \dots, r_m), representing the weights of the leaf nodes 1, 2, (\dots), m.

Then follow (n-1) lines, each containing two integers u and v (1-indexed), indicating an undirected edge between nodes u and v. The given graph forms a tree.

outputFormat

Output a single integer — the minimum possible sum of absolute differences over all edges after optimally assigning weights to the internal nodes.

sample

3 2
5 10
1 3
2 3

5