记录编号	584827	评测结果	AAAATTTTTE
题目名称	树权	最终得分	40
用户昵称	小金	是否通过	未通过
代码语言	C++	运行时间	11.616 s
提交时间	2023-11-16 07:13:21	内存使用	30.53 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=500010;
struct dian{
	long long l=0,r=0;
	//long long e;
}a[N];
int n,m,h[N],ne[N],v[N],tot=0,t=0;
long long ans,r[N],c[2*N];
void add(int x,int y)
{
	tot++;
	v[tot]=y;
	ne[tot]=h[x];
	h[x]=tot;
}
void dfs1(int x,int fa)
{
	if(x<=m)
	{
		return;
	}
	for(int i=h[x];i;i=ne[i])
	{
		int y=v[i];
		{
			if(y!=fa)
			{
				dfs1(y,x);
			}
		}
	}
	t=0;
	memset(c,0,sizeof(c));
	for(int i=h[x];i;i=ne[i])
	{
		int y=v[i];
		{
			if(y!=fa)
			{
				t++;
				c[t]=a[y].l;
				t++;
				c[t]=a[y].r;
			}
		}
	}
	sort(c+1,c+t+1);
	if(t%2==1)
	{
		a[x].l=c[t/2+1];
		a[x].r=c[t/2+1];
	}
	else
	{
		a[x].l=c[t/2];
		a[x].r=c[t/2+1];
	}
	for(int i=h[x];i;i=ne[i])
	{
		int y=v[i];
		if(y!=fa&&(a[y].r<a[x].l||a[y].l>a[x].l))
		{
			
			ans+=min(abs(a[x].l-a[y].r),abs(a[x].l-a[y].l));
		}
	}
	return;
}
int main()
{
	freopen("starria.in","r",stdin);
    freopen("starria.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>r[i];
		a[i].l=r[i];
		a[i].r=r[i];
	}
	dfs1(m+1,0);
	cout<<ans;
	return 0;
}