bzoj1977次小生成树（重要）

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>

#define Maxn 300010

#define maxn 300005

using namespace std;

#define ll long long

struct edge{

    int to,w,nxt;

}edge[Maxn];

int head[Maxn/],tot;

void addedge(int a,int b,int c){

    edge[tot].to=b;

    edge[tot].w=c;

    edge[tot].nxt=head[a];

    head[a]=tot++;

}

struct line{

    int u,v,w;

    bool operator<(const line &a)const{

        return w<a.w;

    }

}q[Maxn];

int vis[Maxn];

int fa[Maxn/];

int findset(int x){

    return fa[x]==x?x:(fa[x]=findset(fa[x]));

}

int unionset(int a,int b){

    return fa[findset(a)]=findset(b);

}

ll d[maxn],f[maxn][],dp[maxn][][];//dp[i][j][0|1]用来表示向上倍增的最大边，严格次大边

void bfs(){

    queue<int>q;

    q.push();

    d[]=;

    while(!q.empty()){

        int x=q.front();q.pop();

        for(int i=head[x];i!=-;i=edge[i].nxt){

            int y=edge[i].to;

            if(d[y])continue;

            d[y]=d[x]+;

            f[y][]=x;

            dp[y][][]=edge[i].w;

            dp[y][][]=-0x3f3f3f3f;

            for(int k=;k<=;k++){

                f[y][k]=f[f[y][k-]][k-];

                int a=dp[y][k-][];//y向上下一半的最大值

                int b=dp[y][k-][];//y向上下一半的严格次大值

                int c=dp[f[y][k-]][k-][];//y向上上一半的最大值

                int d=dp[f[y][k-]][k-][];//y向上上一半的严格次大值

                dp[y][k][]=max(a,c);

                if(a==c)dp[x][k][]=max(b,d);

                else if(a>c)dp[x][k][]=max(c,b);

                else if(a<c)dp[x][k][]=max(a,d);

            }

            q.push(y);

        }

    }

}

inline void calc(ll &val1,ll &val2,ll a,ll b){//更新最大和次大

    if(a<=val1)val2=max(a,val2);

    else val2=val1,val1=a;

}

int lca(int x,int y,int z){//处理加入(x,y,z)后的次小生成树

    ll val1=-,val2=-;

    if(d[x]<d[y])swap(x,y);

    for(int i=;i>=;i--)

        if(d[f[x][i]]>=d[y]){

            calc(val1,val2,dp[x][i][],dp[x][i][]);

            x=f[x][i];

        }

    if(x==y){

        if(val1!=z)return val1;

        return val2;

    }

    for(int i=;i>=;i--)

        if(f[x][i]!=f[y][i]){

            calc(val1,val2,dp[x][i][],dp[x][i][]);

            calc(val1,val2,dp[y][i][],dp[y][i][]);

            x=f[x][i],y=f[y][i];

        }

    calc(val1,val2,dp[x][][],dp[x][][]);

    calc(val1,val2,dp[y][][],dp[y][][]);

    x=f[x][];

    if(val1!=z)return val1;

    else return val2;

}

int main(){

    int n,m;

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

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

        scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);

    sort(q,q+m);

    for(int i=;i<=n;i++) fa[i]=i;

    memset(head,-,sizeof head);

    memset(vis,,sizeof vis);

    tot=;

    int cnt=;

    long long ans=;

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

        int u=q[i].u,v=q[i].v;

        if(findset(u)==findset(v)) continue;

        unionset(u,v);

        vis[i]=;

        addedge(u,v,q[i].w);

        addedge(v,u,q[i].w);

        ans+=q[i].w;

        if(++cnt==n-) break;

    }

    bfs();

    int z=0x3f3f3f3f;

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

        if(!vis[i]) {

            int t=lca(q[i].u,q[i].v,q[i].w);

            if(t>)z=min(z,-t+q[i].w);

        }

    printf("%lld\n",ans+z);

    return ;

}