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
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<functional>
#include<ctype.h>
#include<map>
#define LL long long
#define LD long double
#define L(x) ((x).size())
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
using namespace std;
int n,m,a,b;
LL certain,ncost;
vector<int> v[501000];
int cost[501000];
bool vis1[501000];
bool vis2[501000];
int parent[501000];
vector<int> children[501000];

int vel,START,END;
LL asum,mn,now,last;
vector<int> act;

void count_certain(int x);
void ukorzen(int x,int p);
void licz(int x);
pair<int,int> inv[501000];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n-1;++i){
		scanf("%d%d",&a,&b);
		v[a].PB(b);
		v[b].PB(a);
		}
	for(int i=1;i<=m;++i)
		scanf("%d",&cost[i]);
	count_certain(1);
	for(int i=m+1;i<=n;++i){
		if(!vis2[i]){
			ukorzen(i,0);
			licz(i);
			}
		}
	printf("%lld\n",certain+ncost);
	}
void licz(int x){
    if(x<=m){
		inv[x] = MP(cost[x],cost[x]);
		}
	else{
        for(int i=0;i<L(children[x]);++i)
			licz(children[x][i]);
		act.clear();
		asum = 0;
        for(int i=0;i<L(children[x]);++i){
			act.PB(inv[children[x][i]].FI);
			act.PB(inv[children[x][i]].SE);
			asum+= inv[children[x][i]].FI;
			}
		vel = -L(children[x]);
		sort(act.begin(),act.end());
		last = 0;
		mn = 1e9;mn*=mn;
		for(int i=0;i<L(act);++i){
			now = act[i];
			asum+=(now-last)*vel;
			if(asum<mn){
				mn = asum;
				START = now;
				}
			else if(asum==mn)
				END = now;
			++vel;
			last=now;
			}
		ncost+= mn;
		inv[x].FI = START;
		inv[x].SE = END;
		}
	}
void ukorzen(int x,int p){
    vis2[x] = true;
    parent[x] = p;
    children[p].PB(x);
    if(x>m)
		for(int i=0;i<L(v[x]);++i)
			if(!vis2[v[x][i]])
				ukorzen(v[x][i],x);
	}
void count_certain(int x){
	vis1[x] = true;
    for(int i=0;i<L(v[x]);++i){
        if(!vis1[v[x][i]]){
            if(x<=m && v[x][i]<=m){
				certain+=abs(cost[x]-cost[v[x][i]]);
				}
			count_certain(v[x][i]);
			}
		}
	}