Rail Gauges
Time limit2sMemory limit512 MB
Assign real gauges to domestic stations in a tree whose leaves are foreign stations with fixed gauges, minimizing the sum of absolute differences along edges, and output the floor of the minimum.
Problem
In some ways Byteland is a rather backward country: it still has no railways, while all its neighbouring countries have had them for a long time. This has to change!
Bajtazar, the chief engineer of the newly founded Byteland State Railways, has designed a railway network. The network connects some number of stations in Byteland and some number of stations outside its borders. Each railway connection runs between two stations and is bidirectional. From any station in the network, every other station can be reached in exactly one way, without visiting any station twice.
Unfortunately, the matter is complicated by the fact that every neighbouring country has introduced its own rail gauge standard. It is also impossible to change the rail gauge at any station outside Byteland's borders. For this reason, engineer Bajtazar decided as follows: there will be no common rail gauge standard for all of Byteland; the rail gauge at each Byteland station may be different. On the railway connections between stations, however, BAZRK systems (Byteland Automatic Wheel Gauge Change) will be built, allowing the wheel gauge of a train to be changed while it is moving.
BAZRK systems are, of course, a rather expensive solution; if the rail gauges at two connected stations are r1 and r2 bitometres respectively, then building a BAZRK system on the tracks connecting them costs |r1 − r2| megabytalars.
Help Bajtazar choose the rail gauges at each station in Byteland so as to minimize the total cost of the BAZRK systems.
Input
The first line of input contains two integers n and m (2 ≤ n ≤ 500 000, 1 ≤ m ≤ n), denoting the total number of stations (both Byteland and foreign) in the network and the number of foreign stations, respectively. Foreign stations are numbered from 1 to m, and domestic stations from m + 1 to n.
The following n − 1 lines describe the railway connections between stations: the i-th of these lines contains two integers ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi), meaning that there is a direct railway connection in the network between the stations numbered ui and vi. Every foreign station is connected to exactly one other station, and every domestic station is connected to at least two other stations.
The next m lines contain the rail gauges at the foreign stations: the i-th of these lines contains an integer ri (1 ≤ ri ≤ 500 000) denoting the rail gauge (in bitometres) at the foreign station numbered i.
Output
The only line of output should contain the smallest possible total cost of the installed BAZRK systems in megabytalars, rounded down to the nearest integer.