题意:

有个无向图,问在必选第i条边的情况下,最小生成树是多少?
i会枚举每一个边

题解:

最小生成树好求,Kruskal即可
我们记录最小生成树的值为len
对于边(u,v),如果(u,v)是最小生成树的边,那直接输出答案len
如果不是的话,我们就要去掉最小生成树中从u到v的路径上权值最大的边mlen,然后再加上边(u,v)的边权w,答案就是len-mlen+w
关键就是mlen怎么求?
求树上从u到v的路径上权值最大值
我们可以用倍增的lca
用LCA的思想去完成,我们现在预处理出了一条路上走过的最大值,那么答案所求mx=max(mx(u->w) , mx(v->w)) ;w为u,v的最近公共祖先,这里采用倍增法的思想去完成
树剖也可以吧?貌似是
这个题怎么说,能想到方法,但是不好写,写半小时,调半小时
最烦数据结构的题,愁

代码:

一个代码是网站的题解
还一个是比赛是我同学写的(数据结构大佬)
可读性真高
题解:

#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const maxn=200000,maxm=200000;
int n,m,gra,to[maxn*2+10],val[maxn*2+10],next[maxn*2+10],begin[maxn+10],dep[maxn+10],
    father[maxn+10][20],mx[maxn+10][20],fa[maxn+10],queue[maxn+10];
bool inqueue[maxn+10];
long long ans[maxm+10];
struct rec{int u,v,w,num;};
rec edge[maxm+10];
bool cmp(rec i,rec j){
    return (i.w<j.w)||((i.w==j.w)&&(i.u<j.u))||((i.w==j.w)&&(i.u==j.u)&&(i.v<j.v));
}
int getfather(int x){
    if(!fa[x])return x;
    return fa[x]=getfather(fa[x]);
}
void insert(int u,int v,int w){
    to[++gra]=v;
    val[gra]=w;
    next[gra]=begin[u];
    begin[u]=gra;
}
void bfs(int s){
    int head=0,tail=0;
    inqueue[queue[++tail]=s]=1;
    for(;head!=tail;){
        int now=queue[++head];
        for(int i=begin[now];i;i=next[i])
            if(!inqueue[to[i]]){
                dep[to[i]]=dep[now]+1;
                father[to[i]][0]=now;
                mx[to[i]][0]=val[i];
                inqueue[queue[++tail]=to[i]]=1;
            }
    }
}
int lc(int u,int v){
    int ans=0;
    if(dep[u]<dep[v])swap(u,v);
    fd(i,log(n)/log(2),0)
        if(dep[father[u][i]]>=dep[v]){
            ans=max(ans,mx[u][i]);
            u=father[u][i];
        }
    if(u==v)return ans;
    fd(i,log(n)/log(2),0)
        if(father[u][i]!=father[v][i]){
            ans=max(ans,max(mx[u][i],mx[v][i]));
            u=father[u][i];
            v=father[v][i];
        }
    return max(ans,max(mx[u][0],mx[v][0]));
}
int main(){
    //freopen("street.in","r",stdin);
    //freopen("street.out","w",stdout);
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,1,m)
        scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w),edge[i].num=i;
    sort(edge+1,edge+m+1,cmp);
    fo(i,1,m){
        int fu=getfather(edge[i].u),fv=getfather(edge[i].v);
        if(fu!=fv){
            ans[0]+=edge[i].w;
            ans[edge[i].num]=-1;
            fa[fu]=fv;
            insert(edge[i].u,edge[i].v,edge[i].w);
            insert(edge[i].v,edge[i].u,edge[i].w);
        }
    }
    dep[1]=1;
    bfs(1);
    fo(j,1,log(n)/log(2))
        fo(i,1,n){
            father[i][j]=father[father[i][j-1]][j-1];
            mx[i][j]=max(mx[i][j-1],mx[father[i][j-1]][j-1]);
        }
    fo(i,1,m)
        if(ans[edge[i].num]==-1)ans[edge[i].num]=ans[0];
        else ans[edge[i].num]=ans[0]+edge[i].w-lc(edge[i].u,edge[i].v);
    fo(i,1,m)printf("%lld\n",ans[i]);
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//simplify long long
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
#define inf 2147483647
#define pi 3.14159265358979
#define rep(i, l, r) for(int i = l; i <= r; i ++)
#define lop(i, r, l) for(int i = r; i >= l; i --)
#define step(i, l, r, __step) for(int i = l; i <= r; i += __step)
#define revp(i, r, l, __step) for(int i = r; i >= l; i -= __step)
#define reg regsiter
#define RI regsiter int
#define RL regsiter long long
#define rerep(i, l, r) for(regsiter int i = l; i <= r; i ++)
#define relop(i, r, l) for(regsiter int i = r; i >= l; i --)
#define i8 __int128
#define __int128 ll//don't forget delete it in contest!
inline int read()//fast read
{
    int ret = 0, sgn = 1;
    char chr = getchar();
    while(chr < '0' || chr > '9')
    {if(chr == '-') sgn = -1; chr = getchar();}
    while(chr >= '0' && chr <= '9')
    {ret = ret * 10 + chr - '0'; chr = getchar();}
    return ret * sgn;
}
i8 write(i8 x)//int128's output
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 2e5 + 5;
const int M = 2e5 + 5;
int n,m;
struct edge{
    int from, to;
    ll dis;
    int q;
}e1[M<<1],e2[M<<1];
int head[N],nxt[M<<1],tot1,tot2;
void adde1(int f, int t,ll d)
{
    ++tot1;
    e1[tot1]=(edge){f,t,d,tot1};
}
void adde2(int f,int t,ll d)
{
    e2[++tot2]=(edge){f,t,d,tot2};
    nxt[tot2]=head[f];
    head[f]=tot2;
}
int fa[N];
int find(int a)
{
    if(fa[a]==a) return a;
    return fa[a]=find(fa[a]);
}
bool same(int x, int y)
{
    return find(x)==find(y);
}
void merge(int x,int y)
{
    int fx=find(x),fy=find(y);
    fa[fx]=fy;
}
bool cmp(edge A, edge B)
{
    return A.dis < B.dis;
}
ll dk=0;
void kruskal()
{
    rep(i,1,n) fa[i]=i;
    sort(e1+1,e1+1+m,cmp);
    int cnt=0;
    rep(i,1,m)
    {
    int ff=e1[i].from,tt=e1[i].to;
    ll dd=e1[i].dis;
        if(!same(ff,tt))
        {
            merge(ff,tt);
            adde2(ff,tt,dd);
            adde2(tt,ff,dd);
            cnt++;
            dk+=dd;
            if(cnt==n-1) break;
        }
    }
}
int deep[N],anc[N][23];
ll maxw[N][23];
void dfs(int u, int f)
{
    deep[u]=deep[f]+1;
    anc[u][0]=f;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=e2[i].to;
        if(v==f) continue;
        maxw[v][0]=e2[i].dis;
        dfs(v,u);
    }
}
void init_lca()
{
    for(int j=1;j<=21;j++)
        for(int i=1;i<=n;i++)
        {
            anc[i][j]=anc[anc[i][j-1]][j-1];
            maxw[i][j]=max(maxw[i][j-1],maxw[anc[i][j-1]][j-1]);
        }
}
int lca(int x, int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=21;i>=0;i--)
    {
        if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
    }
    if(x==y) return x;
    for(int i=21;i>=0;i--)
    {
        if(anc[x][i]!=anc[y][i])
            x=anc[x][i], y=anc[y][i];
    }
    return anc[x][0];
}
ll find_maxw(int x, int y)
{
    int c=lca(x,y);
    ll ret=0;
    for(int i=21;i>=0;i--)
    {
        if(deep[anc[x][i]]>=deep[c])
            ret=max(ret,maxw[x][i]), x=anc[x][i];
    }
    for(int i=21;i>=0;i--)
    {
        if(deep[anc[y][i]]>=deep[c])
            ret=max(ret,maxw[y][i]), y=anc[y][i];
    }
    return ret;
}
ll ans[M];
int main()
{
    n=read(),m=read();
    int u,v;
    ll z;
    rep(i,1,m)
    {
        u=read(),v=read();
        scanf("%lld",&z);
        adde1(u,v,z);
    }
    kruskal();
    dfs(1,0);
    init_lca();
//    cout<<dk<<endl;
    rep(i,1,m)
    {
        u=e1[i].from;
        v=e1[i].to;
        if(anc[u][0]==v||anc[v][0]==u) ans[e1[i].q]=dk;
        else
        {
            ll tmp=e1[i].dis + dk - find_maxw(u,v);
            ans[e1[i].q]=tmp;
        }
    }
    rep(i,1,m)
    {
        printf("%lld\n",ans[i]);
    }
    return 0;
}