先入为主给出结论：将 { X i } \{X_i\} {Xi​}离散化后，每条边的影响是一个区间。

然而我并没有想到可行的计算方法。

我真傻，真的。事实上$X_i$变化的本质是边的加入顺序的变化。不妨考虑左端点的情形，首先将边按大小排序，那么对于长度为$W$的边，因为$X_i<W$所以排在$W$之后的边显然不用考虑，不难看出当$X_i$取某个值时，相当于是把前缀的一段边移动到$W$后面去，显然这用一个扫描线就做完了。最后统计答案即可。

复杂度$O(nm+Q)$。

代码比想象中的长。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 2e9
using namespace std;
const int N=505;
const int M=1e5+5;
const int _Q=1e6+5;
int n,m,Q,L[M],R[M],fa[N],dp[N],X[_Q];
ll sum1[_Q],sum2[_Q];
vector<pair<int,int>>G[N];
struct node{int x,y,z;bool operator <(const node &a)const{return z<a.z;}
}f[M];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void addedge(int x,int y,int z){G[x].pb({y,z}),G[y].pb({x,z});
}
void deledge(int x,int y,int z){if(find(G[x].begin(),G[x].end(),make_pair(y,z))!=G[x].end()){G[x].erase(find(G[x].begin(),G[x].end(),make_pair(y,z)));G[y].erase(find(G[y].begin(),G[y].end(),make_pair(x,z)));}
}
void dfs(int u,int topf){for(auto v:G[u]){if(v.fi!=topf){dp[v.fi]=min(dp[u],v.se);dfs(v.fi,u);}}
}
int findedge(int x,int y){dp[x]=inf,dfs(x,0);return dp[y];
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){cin>>f[i].x>>f[i].y>>f[i].z;}sort(f+1,f+1+m);for(int i=1;i<=n;i++)fa[i]=i;//fixedfor(int i=1;i<=m;i++){int x=f[i].x,y=f[i].y,z=f[i].z;if(find(x)!=find(y)){addedge(x,y,i),fa[fa[x]]=fa[y];L[i]=0;}else{int l=findedge(x,y);deledge(f[l].x,f[l].y,l);addedge(x,y,i);L[i]=z+f[l].z;}}for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=n;i++)G[i].clear();reverse(f+1,f+1+m);for(int i=1;i<=m;i++){int x=f[i].x,y=f[i].y,z=f[i].z;if(find(x)!=find(y)){addedge(x,y,i),fa[fa[x]]=fa[y];R[m-i+1]=inf;}else{int l=findedge(x,y);deledge(f[l].x,f[l].y,l);addedge(x,y,i);R[m-i+1]=z+f[l].z;}}reverse(f+1,f+1+m);cin>>Q;for(int i=1;i<=Q;i++)cin>>X[i],X[i]<<=1;for(int i=1;i<=m;i++){int l=upper_bound(X+1,X+1+Q,L[i])-X,r=upper_bound(X+1,X+1+Q,R[i])-X;if(l<r){int p=upper_bound(X+1,X+1+Q,2*f[i].z)-X;sum1[l]+=f[i].z,sum1[p]-=f[i].z;sum2[l]--,sum2[p]++;sum1[p]-=f[i].z,sum1[r]+=f[i].z;sum2[p]++,sum2[r]--;}   }for(int i=1;i<=Q;i++){sum1[i]+=sum1[i-1],sum2[i]+=sum2[i-1];cout<<(sum1[i]+sum2[i]*X[i]/2)<<"\n";}
}