#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
const int lim=510;
const int llim=1e5+100;
const int lllim=1e6+100;
struct {
int parent[lim];
void init(){
for(int i=0;i<lim;i++)parent[i]=i;
}
int find(int i){
if(i==parent[i])return i;
return parent[i]=find(parent[i]);
}
int unite(int i,int j){
i=find(i),j=find(j);
if(i==j)return 0;
parent[i]=j;
return 1;
}
}dsu;
struct edge{
int x,y,z;
};
edge e[llim];
int quer[lllim];
int ans[lllim];
int x;
bool cmp(int i,int j){
int dif1=abs(e[i].z-x);
int dif2=abs(e[j].z-x);
if(dif1!=dif2)return dif1<dif2;
return i<j;
}
void solve(int l,int r,vector<int>&inds){
//cerr<<l<<' '<<r<<'\n';
int mid=l+r>>1;
x=quer[mid];
for(int i=0;i+1<inds.size();i++){
if(cmp(inds[i],inds[i+1]))continue;
sort(inds.begin(),inds.end(),cmp);
break;
}
dsu.init();
//cerr<<"here\n";
vector<int>gol,gor;
for(int i:inds){
//cerr<<e[i].x<<' '<<e[i].y<<'\n';
if(dsu.unite(e[i].x,e[i].y)){
//cerr<<"aaa\n";
ans[mid]+=abs(e[i].z-x);
if(l<=mid-1)gol.pb(i);
if(mid+1<=r)gor.pb(i);
}else if(e[i].z<x){
//cerr<<"www\n";
if(l<=mid-1)gol.pb(i);
}else{
//cerr<<"???\n";
if(mid+1<=r)gor.pb(i);
}
}
if(l<=mid-1)solve(l,mid-1,gol);
if(mid+1<=r)solve(mid+1,r,gor);
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>e[i].x>>e[i].y>>e[i].z;
}
int q;
cin>>q;
for(int i=0;i<q;i++)cin>>quer[i];
vector<int>v;
for(int i=0;i<m;i++)v.pb(i);
solve(0,q-1,v);
for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |