cf测评姬比uva快了五倍。。。
/* 不管这条边是不是在mst上，直接跑lca求出路径上的最大边w即可 ans=mst-w+dist(u,v) */ #include<bits/stdc++.h> using namespace std; #define maxn 100007 struct Edge{int to,nxt,w;}edge[maxn<<1]; struct E{int u,v,w,flag;}e[maxn<<1]; int cmp(E a,E b){return a.w<b.w;} int head[maxn],tot,n,m,q; map<int,int>mp[maxn]; /*4 5 2 1 3*/ void addedge(int u,int v,int w){ edge[tot].w=w; edge[tot].to=v; edge[tot].nxt=head[u]; head[u]=tot++; } int F[maxn]; int find(int x){ return F[x]==-1?x:F[x]=find(F[x]); } int kruskal(){ memset(F,-1,sizeof F); sort(e+1,e+1+m,cmp); int cnt=0,res=0; for(int i=1;i<=m;i++){ int f1=find(e[i].u),f2=find(e[i].v); if(f1==f2)continue; addedge(e[i].u,e[i].v,e[i].w); addedge(e[i].v,e[i].u,e[i].w); res+=e[i].w; F[f1]=f2; if(++cnt==n)break; } return res; } int d[maxn],f[maxn][30],dp[maxn][30]; void bfs(){ memset(d,0,sizeof d); memset(f,0,sizeof f); memset(dp,0,sizeof dp); queue<int>q; q.push(1); d[1]=1; while(!q.empty()){ int x=q.front();q.pop(); for(int i=head[x];i!=-1;i=edge[i].nxt){ int y=edge[i].to; if(d[y])continue; d[y]=d[x]+1; f[y][0]=x; dp[y][0]=edge[i].w; for(int k=1;k<=20;k++){ f[y][k]=f[f[y][k-1]][k-1]; dp[y][k]=max(dp[y][k-1],dp[f[y][k-1]][k-1]); } q.push(y); } } } int lca(int x,int y){//返回路径上的最大边 int res=0; if(d[x]<d[y])swap(x,y); for(int i=20;i>=0;i--) if(d[f[x][i]]>=d[y]){ res=max(res,dp[x][i]); x=f[x][i]; } if(x==y)return res; for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]){ res=max(res,max(dp[x][i],dp[y][i])); x=f[x][i],y=f[y][i]; } res=max(res,max(dp[x][0],dp[y][0])); return res; } void init(){ memset(head,-1,sizeof head); memset(e,0,sizeof e); memset(edge,0,sizeof edge); for(int i=1;i<=n;i++)mp[i].clear(); tot=0; } int main(){ while(scanf("%d%d",&n,&m)==2){ init(); for(int i=1;i<=m;i++){ scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); mp[e[i].u][e[i].v]=mp[e[i].v][e[i].u]=e[i].w; } int mst=kruskal(); bfs(); scanf("%d",&q); while(q--){ int u,v; scanf("%d%d",&u,&v); cout<<mst-lca(u,v)+mp[u][v]<<endl; } } }