1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

const int N = 2007;
int n, m;
vector <int> G[N];
int par[N];
int aa[N];
long long wyn[N][N];
long long plusy[N][N];
long long minusy[N][N];
long long inf = 1e18;
long long addwyn = 0;
int kol[N];
int kol2[N];

void DFS(int v, int p) {
	par[v] = p;
	for(int j = 1; j <= m; ++j) wyn[v][j] = 0;
	for(int i = 0; i < G[v].size(); ++i) {
		if(G[v][i] != p) {
			DFS(G[v][i], v);
			for(int j = 1; j <= m; ++j) {
				long long pom = min(minusy[G[v][i]][j] + aa[kol[j]], plusy[G[v][i]][j] - aa[kol[j]]);
				wyn[v][j] += pom;
			}
		}
	}

	if(G[v].size() == 1) {
		for(int j = 1; j <= m; ++j) wyn[v][j] = inf;
		wyn[v][kol2[v]] = 0;
	}

	minusy[v][0] = inf;
	for(int j = 1; j <= m; ++j) {
		minusy[v][j] = min(minusy[v][j - 1], wyn[v][j] - aa[kol[j]]);
	}
	plusy[v][m + 1] = inf;
	for(int j = m; j > 0; --j) {
		plusy[v][j] = min(plusy[v][j + 1], wyn[v][j] + aa[kol[j]]);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	if(n == m) {
		int a, b;
		cin >> a >> b;
		cin >> a >> b;
		cout << abs(a - b) << endl;
		return 0;
	}
	for(int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	vector <pair <int, int> > wek(m);

	for(int i = 1; i <= m; ++i) {
		cin >> aa[i];
		wek[i - 1] = make_pair(aa[i], i);
	}
	sort(wek.begin(), wek.end());
	for(int i = 0; i < m; ++i) {
		kol[i + 1] = wek[i].second;
		kol2[wek[i].second] = i + 1;
	}
	DFS(n, n);

	long long wynik = inf;
	for(int i = 1; i <= m; ++i) wynik = min(wynik, wyn[n][i]);
	cout << wynik << endl;
	return 0;
}