Connected undirected weighted graph without self-loops and multiple edges is given. Graph contains n vertices and m edges.
For each edge (u, v) find the minimal possible weight of the spanning tree that contains the edge (u, v).
The weight of the spanning tree is the sum of weights of all edges included in spanning tree.
First line contains two integers n and m (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105) — the number of vertices and edges in graph.
Each of the next m lines contains three integers ui, vi, wi (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 109) — the endpoints of the i-th edge and its weight.
Print m lines. i-th line should contain the minimal possible weight of the spanning tree that contains i-th edge.
The edges are numbered from 1 to m in order of their appearing in input.
5 71 2 31 3 11 4 52 3 22 5 33 4 24 5 4
98118889
#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}#define MS(x,y) memset(x,y,sizeof(x))#define MC(x,y) memcpy(x,y,sizeof(x))#define MP(x,y) make_pair(x,y)#define ls o<<1#define rs o<<1|1typedef long long LL;typedef unsigned long long UL;typedef unsigned int UI;template inline void gmax(T1 &a,T2 b){if(b>a)a=b;}template inline void gmin(T1 &a,T2 b){if(bconst int N=2e5+10,Z=1e9+7,ms63=0x3f3f3f3f;int n,m;int first[N],w[N*2],cc[N*2],nxt[N*2];int fa[N],son[N],dep[N],size[N],pos[N],top[N];int f[N];struct C{int l,r,maxv;}c[1<<19];struct edgeedge{int x,y,z;bool operator <(const edgeedge& b)const{return z}}edge[N],M[N];int id,tim;int len[N];//记录每个点到其父节点的边权int pp[N];//记录每个时间戳对应的节点void ins(int x,int y,int z){id++;w[id]=y;cc[id]=z;nxt[id]=first[x];first[x]=id;}int find(int x){return f[x]==x?x:f[x]=find(f[x]);}void build(int o,int l,int r){c[o].l=l;c[o].r=r;if(l==r){c[o].maxv=len[pp[l]];return;}int m=(l+r)>>1;build(ls,l,m);build(rs,m+1,r);c[o].maxv=max(c[ls].maxv,c[rs].maxv);}void dfs1(int x){size[x]=1;son[x]=0;for(int z=first[x];z;z=nxt[z]){int y=w[z];if(y==fa[x])continue;fa[y]=x;len[y]=cc[z];dep[y]=dep[x]+1;dfs1(y);size[x]+=size[y];if(size[y]>size[son[x]])son[x]=y;}}void dfs2(int x,int chain){pos[x]=++tim;pp[tim]=x;top[x]=chain;if(son[x]==0)return;dfs2(son[x],chain);for(int z=first[x];z;z=nxt[z]){int y=w[z];if(y!=fa[x]&&y!=son[x])dfs2(y,y);}}int Qmax(int o,int l,int r){if(c[o].l==l&&c[o].r==r)return c[o].maxv;int m=(c[o].l+c[o].r)>>1;if(r<=m)return Qmax(ls,l,r);else if(l>m)return Qmax(rs,l,r);else return max(Qmax(ls,l,m),Qmax(rs,m+1,r));}int QMAX(int x,int y){int maxv=-1e9;while(top[x]!=top[y]){if(dep[top[x]]gmax(maxv,Qmax(1,pos[top[x]],pos[x]));x=fa[top[x]];}if(pos[x]>pos[y])swap(x,y);if(pos[x]return maxv;}LL MST(){sort(edge+1,edge+m+1);LL sum=0;for(int i=1;i<=m;++i){int x=edge[i].x;int y=edge[i].y;int z=edge[i].z;int fx=find(x);int fy=find(y);if(fx!=fy){f[fy]=fx;ins(x,y,z);ins(y,x,z);sum+=z;}}return sum;}int main(){while(~scanf("%d%d",&n,&m)){id=0;for(int i=1;i<=n;++i){f[i]=i;first[i]=0;}for(int i=1;i<=m;++i)scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);MC(M,edge);LL sum=MST();fa[1]=0;dep[1]=0;dfs1(1);tim=0;dfs2(1,1);build(1,1,n);for(int i=1;i<=m;++i){LL ans=sum-QMAX(M[i].x,M[i].y)+M[i].z;printf("%lld\n",ans);}}return 0;}/*【trick&&吐槽】明明是权在边上，可是被我写成了权在点上。本来又是可以绝杀的，然而还是跪掉了TwT【题意】给你一个无向连通图，n（2e5）个点，m（n-1<=m<=2e5）条边，且不存在重边和自环。这个图显然可以有最小生成树。我们问你，假如说我们必须要求第1~m条边是这个最小生成树上的边，那么在这个基础上会形成的最小生成树的权值是多少？也就是说，我们有m个输出。第i个输出，表示在我们要求第i条边必须是最小生成树上的树边的基础上，形成的最小生成树的边权和。【类型】树链剖分【分析】这道题的询问是如此之多。我们发现，其实它们都是基于最小生成树，然后再做一点点修改而已。于是，我们不妨先求出最小生成树。然后，如果我们要求第i条边在这个树上，那么我们再加上第i条边，就会形成一个环。我们想要去掉一个环，于是，我们只需要移除这个环上的任意一条边即可。而新加的那条边（x，y），我们是不能移除的，于是，我们移除的相当于原来最小生成树链（x，y）上的任一条边。显然，为了实现最小生成树的构成，我们会选择移除其中边权最大的那条边。于是，只要实现—— 树链剖分，权在边上，链上最大边 的功能，这道题就可以AC啦。【时间复杂度&&优化】O（mlognlogn）*/
京公网安备 11010802041100号