Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie. 
  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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>

//#define DBG

using namespace std;

int n, m;

struct Stacja {
  bool krajowa;
  int r;
  vector<int> drogi;
  bool ok;  // czy jeszcze j� bra� pod uwag� (zagraniczne w og�le nie bior� udzia�u)
  int ile;  // ile stacji s�siaduje (w pierwszej fazie chodzi o zagraniczne, a w drugiej o nieprzeanalizowane krajowe)
  map<int, int> *Z; // zale�no�� kosztu grupy od rozstawu w tej stacji (rozstaw, zmiana gradientu kosztu)
  int opt;          // optymalny rozstaw w stacji dla grupy (ewentualnie kolejny z Z te� jeszcze jest optymalny)
  int g;            // gradient w poprzednim przedziale przed opt
};

Stacja *s;

//////////////////////////////////////////////////////////////////////////////////////
#ifdef DBG
void pisz() {
  printf("n=%d, m=%d\n", n, m);
  for (int i = m; i < n; ++i) if (s[i].ok) {
    printf("  %d. ile=%d [", i, s[i].ile);
    vector<int> &drogi = s[i].drogi;
    for (int j = 0; j < drogi.size(); ++j) if (s[drogi[j]].ok) printf("%d ", drogi[j]);
    printf("] [");
    for (int j = 0; j < drogi.size(); ++j)
      if (!s[drogi[j]].krajowa) printf("%d ", drogi[j]);
    printf("]\n");
  }
}
void piszZ(int i)
{
  printf("  size=%d [", s[i].Z->size());
  map<int, int>::iterator xx = s[i].Z->begin();
  while (xx != s[i].Z->end()) {
    printf("(%d, %d) ", xx->first, xx->second);
    xx++;
  }
  printf("]\n");
}

#endif // DBG

//////////////////////////////////////////////////////////////////////////////////////
// wyznacza g�rn� granic� zakresu optymalnego dla stacji i
inline int opt_max(int i)
{
  int opt2 = s[i].opt; // na pocz�tek mo�na ustawi� doln� granic�
  map<int, int>::iterator it = s[i].Z->find(opt2); // musi by�
  if (s[i].g + it->second == 0) { // jest gradient zerowy do kolejnego punktu
    it++;
    if (it == s[i].Z->end())
      opt2 = 500000;
    else
      opt2 = it->first;
  }
  return opt2;
}


//////////////////////////////////////////////////////////////////////////////////////

inline void dodaj(map<int, int> *Z, int r, int d, int stary_opt = -1)
{
  map<int, int>::iterator it = Z->find(r);
  if (it == Z->end()) {
    Z->insert(pair<int, int>(r, d));   // je�li nie ma to dodaj
  }
  else { // je�li jest to zmodyfikuj warto��
    d += it->second;
    Z->erase(it);
    // nie dodawaj je�li wyjdzie zero chyba, �e to stary opt, kt�ry zachowujemy
    if (d != 0 || r == stary_opt) Z->insert(pair<int, int>(r, d));
  }
}

long long licz()
{
  /*
    Informacja o zale�no�ci kosztu grupy od rozstawu na skrajnej stacji b�dzie pami�tana w formie:
      map<int, int> - (rozstaw, zmiana gradientu w stosunku do poprzedniego przedzia�u)
      int - optymalny rozstaw
            ostatni z mapy, dla kt�rego suma narastaj�co dla poprzednich warto�ci jest < 0
      int - ten ujemny gradient
    Znajd� te stacje, kt�re ��cz� si� z zagranicznymi.
      Zainicjuj dla nich informacj� o zale�no�ci:
        wrzu� (0, -n) oraz (ri, 2) dla ka�dej stacji zagranicznej i=1..n
        przejd� po mapie i znajd� optymalny
    Dla pozosta�ych zainicjuj na pusto.
    Na PQ wrzu� wszystkie nieprzeanalizowane stacje z kluczem w postaci liczby nieprzeanalizowanych
    krajowych kt�rymi si� ��cz� i wybieraj kolejno stacje A (a� zostanie jedna):
      Usu� z PQ.
      Znajd� jedyn� nieprzeanalizowan� sasiaduj�c� B.
      Do��cz informacje o zale�no�ci A do B.
      Je�li ta B nie ma swojej zale�no�ci to tylko bierze zakres opt z A.
      Oznacz A jako przeanalizowan� i popraw liczb� nieprzeanalizowanych s�siednich dla B (w PQ).
    Jak w PQ jest jedna stacja to od niej zaczynamy obliczanie kosztu:
      Ustaw jej rozstaw na warto�� optymaln� (jak jest przedzia� to oboj�tnie).
      Przejd� od niej BSF wszystkie krajowe:
        Wchodz�c na stacj� krajow� (tzn. wychodz�c do niej z ju� policzonej)
          Ustaw jej rozstaw na optymalny, a je�li przedzial wybierz warto�� bli�sz�
          rozstawowi na stacji, z kt�rej wychodzimy.
          Dolicz koszt po��czenia do wyniku.
  */

  set<pair<int, int> > PQ;   // kolejka priorytetowa  (liczba nieprzeanalizowanych s�siednich, numer stacji)
  int i, j;

  // obliczenie zale�no�ci kosztu od rozstawu dla pojedynczych stacji (uwzgl�dniaj�c tylko zagraniczne)
  for (i = m; i < n; ++i) if (s[i].ok) {
    #ifdef DBG
    printf("obliczam zaleznosci i=%d\n", i);
    #endif // DBG
    vector<int> &drogi = s[i].drogi;
    s[i].Z = new map<int, int>();
    if (s[i].ile > 0) { // ma zagraniczne (UWAGA: nie ka�da musi mie�)
      dodaj(s[i].Z, 0, -s[i].ile);
      for(j = 0; j < drogi.size(); ++j)
        if (!s[drogi[j]].krajowa) dodaj(s[i].Z, s[drogi[j]].r, 2);
      #ifdef DBG
      piszZ(i);
      #endif // DBG
      map<int, int>::iterator it = s[i].Z->begin();
      s[i].opt = 0;
      s[i].g = 0;
      int g = it->second; // gradient w kolejnym przedziale (teraz w pierwszym od 0)
      #ifdef DBG
      printf("  g=%d\n", g);
      #endif // DBG
      it++; // patrzymy od nast�pnego rozstawu
      for(; g < 0 && it != s[i].Z->end(); it++) {
        s[i].opt = it->first;
        s[i].g = g;
        g += it->second;
      }
      // zatrzymujemy si� na g >= 0 czyli poprzedni zapami�tamy by� ostatnim z g < 0
      #ifdef DBG
      printf("  opt=%d, g=%d\n", s[i].opt, s[i].g);
      #endif // DBG
    }
    else {  // oznaczenie, �e nie mia�a zagranicznych
      s[i].opt = -1;
      s[i].g = 0;
    }

    s[i].ile = 0; // teraz liczymy s�siednie krajowe
    for (j = 0; j < drogi.size(); ++j) if (s[drogi[j]].ok && s[drogi[j]].krajowa) s[i].ile++;
    PQ.insert(pair<int, int>(s[i].ile, i));
    #ifdef DBG
    printf("  wstawiam ile=%d, stacja=%d\n", s[i].ile, i);
    #endif // DBG
  }
  #ifdef DBG
  printf("PQ.size()=%d\n", PQ.size());
  {
    set<pair<int, int> >::iterator xx = PQ.begin();
    printf("%d\n", xx->first);
  }
  #endif // DBG

  // ��czenie grup stacji - do��czamy zawsze tak� co ma tylko jedn� drog� do nieprzeanalizowanej
  while (PQ.size() > 1) {   // a� zostanie tylko jedna grupa
    set<pair<int, int> >::iterator it = PQ.begin();
    int A = it->second; // numer stacji do��czanej
    PQ.erase(it);
    // znajd� nieprzeanalizowan� s�siedni� krajow� (musi by�)
    for (i = 0; !s[s[A].drogi[i]].ok; ++i);
    int B = s[A].drogi[i]; // numer stacji do kt�rej do��czamy
    #ifdef DBG
    printf("dolacz A=%d B=%d\n", A, B);
    piszZ(A);
    piszZ(B);
    #endif // DBG

    // wyznaczy� dla A zakres minimalny i doda� zmiany gradientu
    int g0 = s[B].g;  // poprzedni gradient przed punktem optymalnym
    int Amin = s[A].opt;
    int Amax = opt_max(A);
    int t3[3] = {0, Amin, Amax};
    int d3[3] = {-1, 1, 1};
    int B_stary_opt = s[B].opt;

    if (B_stary_opt == -1) {  // stacja bez zagranicznych
      for (i = 0; i < 3; ++i) {
        dodaj(s[B].Z, t3[i], d3[i]);
      }
      s[B].opt = Amin;
      s[B].g = -1;
    }
    else {
      map<int, int>::iterator it_opt = s[B].Z->find(B_stary_opt);
      int g2 = g0 + it_opt->second; // gradient w przedziale za doln� granic� zakresu optymalnego (poprzedni = przed aktualizacj�)
      #ifdef DBG
      printf("  g0=%d, g2=%d, Amin=%d, Amax=%d, Bopt=%d\n", g0, g2, Amin, Amax, B_stary_opt);
      #endif // DBG
      for (i = 0; i < 3; ++i) {
        dodaj(s[B].Z, t3[i], d3[i], B_stary_opt); // nie usuwaj starej granicy zakres u optymalnego bo potrzebne
        if (t3[i] <  B_stary_opt) g0 += d3[i];
        if (t3[i] <= B_stary_opt) g2 += d3[i];
      }
      #ifdef DBG
      printf("  g0=%d, g2=%d\n", g0, g2);
      #endif // DBG
      // teraz trzeba zaktualizowa� doln� granic� przedzia�u optymalnego oraz gradient dla B
      it_opt = s[B].Z->find(B_stary_opt); // znale�� na nowo po zmianach w strukturze
      // sprawdzamy czy zmiana gradientu w starym opt nie wysz�a zerowa bo je�li tak to on do usuni�cia
      bool usun_stary_opt = (it_opt->second == 0);
      if (g0 == 0) {
        // I. gradient przed poprzednim optymalnym by� < 0, ale m�g� si� wyzerowa� i trzeba si� cofn��
        it_opt--;
        s[B].opt = it_opt->first;
        s[B].g = - it_opt->second;
      }
      else if (g2 < 0) {
        // II. gradient za tym punktem by� >= 0, ale m�g� spa�� < 0 i trzeba si� przesun�� do przodu
        it_opt++;
        s[B].opt = it_opt->first;
        s[B].g = g2;
      }
      else {
        // nic si� nie przesun�o, ale trzeba zaktualizowa� gradient
        s[B].g = g0;
      }
      if (usun_stary_opt) {
        #ifdef DBG
        if (s[B].opt == B_stary_opt) {
          printf ("  !!! usuwamy opt!\n");
          exit(0);
        }
        #endif // DBG
        s[B].Z->erase(B_stary_opt);
      }
      #ifdef DBG
      {
        piszZ(B);
        int opt2 = opt_max(B);
        if (opt2 > s[B].opt)
          printf("  opt=(%d, %d) g=%d\n", s[B].opt, opt2, s[B].g);
        else
          printf("  opt=%d, g=%d\n", s[B].opt, s[B].g);

        // sprawdzenie "na piechot�"
        map<int, int>::iterator spr_it = s[B].Z->begin();
        int spr_opt = 0;
        int spr_g = 0;
        int g = spr_it->second; // gradient w kolejnym przedziale (teraz w pierwszym od 0)
        spr_it++; // patrzymy od nast�pnego rozstawu
        for(; g < 0 && spr_it != s[B].Z->end(); spr_it++) { // zatrzymujemy si� na warto�ci >= 0
          spr_opt = spr_it->first;                          // czyli poprzedni zapami�tamy by� ostatnim < 0
          spr_g = g;
          g += spr_it->second;
          //printf("    r=%d, g=%d, gnar=%d\n", spr_opt, spr_it->second, g);
        }
        if (spr_opt != s[B].opt || spr_g != s[B].g) {
          printf("  !!!! ma byc: opt=%d g=%d\n", spr_opt, spr_g);
          exit(0);
        }
      }
      #endif // DBG
    }

    s[A].ok = false; // ju� przeanalizowana
    // aktualizowa� liczb� po��cze� z B do nieprzeanalizowanych i poprawi� w PQ
    PQ.erase(pair<int, int>(s[B].ile, B));
    s[B].ile--;
    PQ.insert(pair<int, int>(s[B].ile, B));
  }

  // teraz ju� tylko ustalenie optymalnych rozstaw�w i policzenie kosztu
  int A = PQ.begin()->second; // ostatnia stacja od kt�rej zaczynamy teraz ustawianie rozstaw�w
  s[A].r = s[A].opt; // ustawiamy w stacji rozstaw optymalny dla ca�ej grupy
  long long wyn = 0;
  queue<int> q;
  q.push(A);
  while (q.size()) {
    A = q.front(); // kolejna odwiedzana stacja
    q.pop();
    vector<int> &drogi = s[A].drogi;
    for (i = 0; i < drogi.size(); ++i) {
      int B = drogi[i]; // s�siednia
      if (s[B].r == -1) { // odwied� s�siednie (krajowe) co nie maj� r
        if (s[A].r <= s[B].opt)
          s[B].r = s[B].opt; // we� doln� granic� zakresu optymalnego dla B
        else { // s[B].opt < s[A].r
          // jak si� da to we� to samo co w A a jak nie to g�rna granica b�dzie lepsza ni� dolna
          s[B].r = min(s[A].r, opt_max(B));
        }
        q.push(B);
        wyn += abs(s[A].r - s[B].r); // dolicz koszt
      }
      else if (!s[B].krajowa)
        wyn += abs(s[A].r - s[B].r); // dolicz koszt do zagranicznej
      #ifdef DBG
      else
        continue;
      printf("BAZRK(%d, %d) = %d\n", A, B, abs(s[A].r - s[B].r));
      #endif // DBG
    }
  }
  #ifdef DBG
  long long spr_wyn = 0;
  for (i = m; i < n; ++i) if (s[i].r <= 500000) {
    printf("r[%d] = %d\n", i, s[i].r);
    vector<int> &drogi = s[i].drogi;
    for (int j = 0; j < drogi.size(); ++j) {
      int cel = drogi[j];
      if (cel < i  &&  s[cel].r <= 500000)
        spr_wyn += abs(s[i].r - s[cel].r);
    }
  }
  printf("spr_wyn=%I64d\n", spr_wyn);
  #endif // DBG
  return wyn;
}

//////////////////////////////////////////////////////////////////////////////////////
void czytaj()
{
  int i;
  scanf("%d%d", &n, &m);
  s = new Stacja[n];
  for (i = 0; i < n; ++i) {
    s[i].ok = s[i].krajowa = (i >= m);
    s[i].drogi = vector<int>();
    s[i].ile = 0;
    s[i].Z = NULL;
    s[i].r = -1; // niepoliczona
  }
  for (i = 0; i < n - 1; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--; b--;
    s[a].drogi.push_back(b);
    s[b].drogi.push_back(a);
    if (!s[a].krajowa) s[b].ile++;
    if (!s[b].krajowa) s[a].ile++;
  }
  for (i = 0; i < m; ++i) scanf("%d", &s[i].r);
  #ifdef DBG
  pisz();
  #endif // DBG
}

int main()
{
  czytaj();
  if (n == 2 && m == 2) {  // uff
    printf("%d\n", abs(s[0].r - s[1].r));
    return 0;
  }
  //redukuj();  -- trudno b�dzie bez redukcji bo co� zwali�em
  long long wyn = licz();
  printf("%lld\n", wyn);
  return 0;
}