题意：一个无向图联通中，求包含每条边的最小生成树的值（无自环，无重边）
分析：求出这个图的最小生成树，用最小生成树上的边建图
对于每条边，不外乎两种情况
1：该边就是最小生成树上的边，那么答案显然
2：该边不在最小生成树上，那么进行路径查询，假设加入这条边，那么形成一个环，删去这个环上除该边外的最大权值边，形成一棵树
树的权值即为答案。（并不需要真正加入这条边）
注：其实用树链剖分和LCA都可以，选择自己熟悉的写就行，我写的树链剖分
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cstdlib> #include<cmath> using namespace std; typedef long long LL; const int maxn=200005; int n,m; LL mst; struct Edge { int w,v,next; } edge[maxn<<1]; struct E { int u,v,w,id,mark; void init(int a,int b,int c,int d) { u=a,v=b,w=c,id=d,mark=0; } } o[maxn]; bool cmp1(E a,E b) { return a.id<b.id; } bool cmp2(E a,E b) { return a.w<b.w; } int head[maxn],p; void addedge(int u,int v,int w) { edge[p].v=v; edge[p].w=w; edge[p].next=head[u]; head[u]=p++; } int fa[maxn],sz[maxn],id[maxn],dep[maxn],top[maxn],son[maxn],clk; int ww[maxn],re[maxn]; void dfs1(int u,int f,int d) { fa[u]=f; sz[u]=1; son[u]=-1; dep[u]=d; for(int i=head[u]; ~i; i=edge[i].next) { int v=edge[i].v; if(v==f)continue; dfs1(v,u,d+1); sz[u]+=sz[v]; if(son[u]==-1||sz[v]>sz[son[u]]) son[u]=v,re[u]=edge[i].w; } } void dfs2(int u,int tp,int cc) { id[u]=++clk; top[u]=tp; ww[id[u]]=cc; if(son[u]!=-1)dfs2(son[u],tp,re[u]); for(int i=head[u]; ~i; i=edge[i].next) { int v=edge[i].v; if(v==son[u]||v==fa[u])continue; dfs2(v,v,edge[i].w); } } int maxw[maxn<<2]; void pushup(int rt) { maxw[rt]=max(maxw[rt*2],maxw[rt*2+1]); } void build(int rt,int l,int r) { if(l==r) { maxw[rt]=ww[l]; return; } int m=(l+r)>>1; build(rt*2,l,m); build(rt*2+1,m+1,r); pushup(rt); } int query(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y) return maxw[rt]; int m=(l+r)>>1; int ans=-1; if(x<=m)ans=max(ans,query(rt*2,l,m,x,y)); if(y>m)ans=max(ans,query(rt*2+1,m+1,r,x,y)); return ans; } int getans(int u,int v) { int ans=-1; while(top[u]!=top[v]) { if(dep[top[u]]<dep[top[v]])swap(u,v); ans=max(ans,query(1,1,n,id[top[u]],id[u])); u=fa[top[u]]; } if(dep[u]>dep[v])swap(u,v); ans=max(ans,query(1,1,n,id[son[u]],id[v])); return ans; } int fat[maxn]; int find(int x) { if(x==fat[x])return x; return fat[x]=find(fat[x]); } void init() { for(int i=1; i<=n; ++i) fat[i]=i; mst=p=clk=0; memset(head,-1,sizeof(head)); } int main() { while(~scanf("%d%d",&n,&m)) { init(); for(int i=0; i<m; ++i) { int u,v,w; scanf("%d%d%d",&u,&v,&w); o[i].init(u,v,w,i); } sort(o,o+m,cmp2); int cnt=0; for(int i=0; i<m; ++i) { int fx=find(o[i].u); int fy=find(o[i].v); if(fy==fx)continue; addedge(o[i].u,o[i].v,o[i].w); addedge(o[i].v,o[i].u,o[i].w); cnt++; o[i].mark=1; fat[fy]=fx; mst+=o[i].w; if(cnt>=n-1)break; } dfs1(1,-1,1); dfs2(1,1,0); build(1,1,n); sort(o,o+m,cmp1); for(int i=0; i<m; ++i) { if(o[i].mark)printf("%I64d ",mst); else { int tt=getans(o[i].u,o[i].v); printf("%I64d ",mst-tt+o[i].w); } } } return 0; }