| 比赛 |
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;
}