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