[Educational Round 3][Codeforces 609E. Minimum spanning tree for each edge]

这题本来是想放在educational round 3的题解里的，但觉得很有意思就单独拿出来写了

题目链接：609E - Minimum spanning tree for each edge

题目大意：n个点，m条边，对每条边，询问包含此边的最小生成树的边权之和

题解：大部分人都是用LCA写的，这里提供一个更为精妙的做法。

　　　模拟Kruskal算法建MST的过程，先将m条边按边权排序，依次进行判断。若点对(u,v)属于同一个连通块，则加入边{u,v,w}后会形成一个环，把环中最大的边换成w会多产生的权重就是包含这条边的MST比原先的MST多出来的权重，否则在MST中加入这条边。

　　　而这里加边的时候并不是选择直接在(u,v)之间连边，而是在他们的祖先之间连边，并有如下判断：若点v的子树大小大于点u的子树大小，则把v看做是u的父亲（将u所在的子树并入v），反之亦然。判断加边后是否会成环时，则只需暴力一层层寻找当前点的父亲即可，即是用O(n)的方法求LCA，但由于之前建树的方式用到了[small to large]的思想（就是启发式合并），所以往上爬的层数不会超过log n。因此时间复杂度为O(mlog n)。

#include<bits/stdc++.h>

using namespace std;

#define N 200001

#define LL long long

struct rua{LL u,v,w,id;}a[N];

LL n,m,mst,fa[N],f[N],sz[N],l[N];

bool cmp(rua x,rua y){return x.w<y.w;}

LL add(LL u,LL v,LL w)

{

    LL mx=;

    while((fa[u]!=u ||fa[v]!=v) && u!=v)

      if(fa[u]==u || (fa[v]!=v && sz[v]<=sz[u]))

        mx=max(mx,l[v]),v=fa[v];

      else mx=max(mx,l[u]),u=fa[u];

    if(u==v)return w-mx;

    if(sz[u]<sz[v])swap(u,v);

    sz[u]+=sz[v],fa[v]=u,l[v]=w;

    return mst+=w,;

}

int main()

{

    scanf("%I64d%I64d",&n,&m);

    for(int i=;i<=m;i++)

      scanf("%I64d%I64d%I64d",&a[i].u,&a[i].v,&a[i].w),sz[i]=,fa[i]=a[i].id=i;

    sort(a+,a+m+,cmp);

    for(int i=;i<=m;i++)

      f[a[i].id]=add(a[i].u,a[i].v,a[i].w);

    for(int i=;i<=m;i++)

      printf("%I64d\n",mst+f[i]);

}