比赛 2025.12.20 评测结果 AAAAAAAAAA
题目名称 cogito的树 最终得分 100
用户昵称 zcx 运行时间 1.688 s
代码语言 C++ 内存使用 31.82 MiB
提交时间 2025-12-20 10:15:32
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int M=5e5+2;
typedef long long ll;
ll l[M],r[M],tool[M],ans=0,root;
ll n,m;
vector<int> g[M];
bool cmp(ll a,ll b){
	return a<b;
}
void dfs(ll num,ll p){
	if(num<=m) return; 
	int k=0;
	for(int i=0;i<g[num].size();i++){
		int o=g[num][i];
		if(o==p) continue;
		dfs(o,num);
	}
	for(int i=0;i<g[num].size();i++){
		int o=g[num][i];
		if(o==p) continue;
		tool[++k]=l[o];
		tool[++k]=r[o];
	}
//	if(num==5) for(int i=1;i<=k;i++) cout<<tool[i]<<" ";
	sort(tool+1,tool+1+k,cmp);
//	if(num==5){
//		cout<<endl;
//		for(int i=1;i<=k;i++) cout<<tool[i]<<" ";
//	}
	l[num]=tool[k/2];
	r[num]=tool[k/2+1];
	ll an=0;
	for(int i=0;i<g[num].size();i++){
		int o=g[num][i];
		if(o==p) continue;
		if(!(l[num]<=r[o]&&l[num]>=l[o])) an+=min(abs(l[num]-l[o]),abs(l[num]-r[o]));
	}
	ans+=an;
}
int main()
{
	freopen("starria.in","r",stdin);
	freopen("starria.out","w",stdout);
	cin>>n>>m;
	if(n==m){
		cout<<0<<endl;
		return 0;
	}
	root=m+1;
	for(int i=1;i<=n-1;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=m;i++){
		scanf("%lld",l+i);
		r[i]=l[i];
	}
	dfs(root,0);
//	cout<<endl;
//	cout<<l[1]<<"   "<<r[1]<<endl;
	cout<<ans<<endl;
	return 0;
}