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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
using namespace std;
typedef long long ll;
typedef double db;
const db pi=acos(-1);
void gn(int &x){
    int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')sg=-1,x=0;else x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';
    x*=sg;
}
void gn(ll &x){
    int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c=='-')sg=-1,x=0;else x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';
    x*=sg;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int n,m;

struct edge{
	int v,next;
}e[1000005];int etot=0;
int g[500005];
void ae(int u,int v){
	e[etot].v=v;e[etot].next=g[u];g[u]=etot++;
}

ll f[500005];
int l[500005],r[500005];


int qu[500005];int p,q;int pre[500005];



int t[1000005];int tot;
void dp(int u){
	if(l[u])return;
	ll su=0;
	tot=0;
	for (int i=g[u];~i;i=e[i].next)if(e[i].v!=pre[u]){
		su+=f[e[i].v];
		t[++tot]=l[e[i].v];
		t[++tot]=r[e[i].v];
	}
	sort(t+1,t+1+tot);
	l[u]=t[tot/2];
	r[u]=t[tot/2+1];
	for (int i=g[u];~i;i=e[i].next)if(e[i].v!=pre[u]){
		if(l[u]>r[e[i].v])su+=l[u]-r[e[i].v];
		else if(l[u]<l[e[i].v])su+=l[e[i].v]-l[u];
	}
	f[u]=su;
}
ll bfs(int rt){
	p=q=0;
	qu[q++]=rt;
	pre[rt]=0;
	while(p!=q){
		int u=qu[p++];
		for (int i=g[u];~i;i=e[i].next)if(e[i].v!=pre[u]){
			pre[e[i].v]=u;
			qu[q++]=e[i].v;
		}
	}
	for (int i=q-1;i>=1;i--)dp(qu[i]);

	int v=qu[1];
	ll su=f[v];
	if(l[1]>r[v])su+=l[1]-r[v];
	else if(l[1]<l[v])su+=l[v]-l[1];
	return su;
}

int main()
{
	memset(g,-1,sizeof(g));
	scanf("%d%d",&n,&m);
	for (int i=1;i<n;i++){
		int u,v;
		gn(u);gn(v);
		ae(u,v);
		ae(v,u);
	}
	for (int i=1;i<=m;i++){
		gn(l[i]);
		r[i]=l[i];
	}
	cout<<bfs(1)<<endl;
	return 0;
}