比赛 2025.12.20 评测结果 AAAAAAAAAA
题目名称 cogito的树 最终得分 100
用户昵称 汐汐很希希 运行时间 4.123 s
代码语言 C++ 内存使用 57.66 MiB
提交时间 2025-12-20 10:59:24
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+10;
const int M=0;
const int MOD=998244353;
const int MAXX=2e9;
ll n,m,v[N],L[N],R[N],ans=0;
vector<ll> g[N];
vector<ll> e[N];
void add(ll x,ll y,ll w=0){
	g[x].push_back(y);
	e[x].push_back(w);
}
void dfs(ll u,ll fa)
{
	vector<ll> q;
	if(u<=m) return;
	for(int i=0;i<g[u].size();i++)
	{
		ll v=g[u][i];
		if(v==fa) continue;
		dfs(v,u);
		q.push_back(L[v]),q.push_back(R[v]); 
	}
	sort(q.begin(),q.end());
	ll len=q.size();
	if(len%2==1) L[u]=R[u]=q[len/2];
	else L[u]=q[len/2-1],R[u]=q[len/2];
	for(int i=0;i<e[u].size();i++)
	{
		ll v=g[u][i];
		if(v==fa) continue;
		if(L[u]>R[v]) ans+=L[u]-R[v];
		else if(L[u]<L[v]) ans+=L[v]-L[u];	
		else ans+=0;
	} 
}
int main()
{
	freopen("starria.in","r",stdin);
	freopen("starria.out","w",stdout);
	
	cin>>n>>m; 
	for(int i=1;i<n;i++){
		ll a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	for(int i=1;i<=m;i++) cin>>v[i],L[i]=R[i]=v[i];
	if(n==2) cout<<abs(v[1]-v[2])<<'\n';
	else{
		dfs(m+1,0);
		cout<<ans<<'\n';
	}
	return 0;
}