比赛 2025.12.20 评测结果 AAAAAAAAAA
题目名称 cogito的树 最终得分 100
用户昵称 梦那边的美好ME 运行时间 1.442 s
代码语言 C++ 内存使用 25.15 MiB
提交时间 2025-12-20 11:28:13
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll w[510000];
ll l[510000],r[510000];
ll n,m,ans;
ll head[1010000],nxt[1010000],to[1010000],cnt;

void add(ll u,ll v){
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    to[++cnt]=u;
    nxt[cnt]=head[v];
    head[v]=cnt;
} 

void dfs(ll u,ll fa){
	vector<ll> ls;
	if(u<=m) return;
	for(int i=head[u];i;i=nxt[i]){
		ll v=to[i];
        if(v==fa) continue;
		dfs(v,u);
		ls.push_back(l[v]),ls.push_back(r[v]); 
	}
	sort(ls.begin(),ls.end());
	ll sz=ls.size();
	if(sz%2==1){
        l[u]=r[u]=ls[sz/2];
    }else{
        l[u]=ls[sz/2-1];
        r[u]=ls[sz/2];
    }
	for(int i=head[u];i;i=nxt[i]){
        ll v=to[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];
	}
}

int main(){
    freopen("starria.in","r",stdin);
    freopen("starria.out","w",stdout);
	ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		ll u,v;
        cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=m;i++){
        cin>>w[i];
        l[i]=w[i];r[i]=w[i];
    }
	if(n==2){
		cout<<abs(w[1]-w[2])<<'\n';
		return 0;
	}
	dfs(m+1,0);
	cout<<ans<<'\n';
	return 0;
} 


/*

6 4 
1 5 
2 5 
3 6 
4 6 
5 6 
5 
10 
20 
40



*/