Street

Description

給出n個點,m條有權邊,現對于每一條邊，你需要回答出包含這條邊的最小生成樹的總邊權值。

n,m<=2*10^5

Solution

題解和題意一樣簡潔系列。

首先求出mst，然後對于每一條不在mst裡面的邊，相當于把它和mst中的一條邊替換。

若是(x,y)這條邊，那麼就是在生成樹中x到y的路徑上選擇一條邊權最大的邊替換。

倍增最大值即可。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define N 200005
using namespace std;
typedef long long ll;
struct note{int x,y,v,id;}e[N];
bool cmp(note x,note y) {return x.v<y.v;}
int n,m,x,y,z,tot,cnt,l,q[N],ask[N],d[N],fa[N];
int last[N],v[N*2],next[N*2],t[N*2],f[N][],g[N][];
bool bz[N];
ll ans,an[N];
int get(int x) {return fa[x]?fa[x]=get(fa[x]):x;}
void add(int x,int y,int z) {
    t[++l]=y;v[l]=z;next[l]=last[x];last[x]=l;
}
int lca(int x,int y) {
    if (d[x]<d[y]) swap(x,y);int ans=;
    fd(j,,) if (d[g[x][j]]>d[y]) ans=max(ans,f[x][j]),x=g[x][j];
    if (d[x]!=d[y]) ans=max(ans,f[x][]),x=g[x][];
    fd(j,,) if (g[x][j]!=g[y][j]) 
    ans=max(ans,max(f[x][j],f[y][j])),x=g[x][j],y=g[y][j];
    if (x!=y) return max(ans,max(f[x][],f[y][]));else return ans;
}
int main() {
    freopen("street.in","r",stdin);
    freopen("street.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,,m) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v),e[i].id=i;
    sort(e+,e+m+,cmp);
    fo(i,,m) {
        int a=get(e[i].x),b=get(e[i].y);
        if (a!=b) fa[a]=b,tot++,ans+=(ll)e[i].v,bz[i]=;
        if (tot==n-) break;
    }
    fo(i,,m) if (bz[i]) {
        add(e[i].x,e[i].y,e[i].v);
        add(e[i].y,e[i].x,e[i].v);
        an[e[i].id]=ans;
    } else ask[++cnt]=i;
    int i=,j=;q[1]=d[]=;
    while (i<j) 
        rep(k,q[++i]) if (t[k]!=g[q[i]][]) {
            g[t[k]][]=q[i];f[t[k]][]=v[k];
            d[t[k]]=d[q[i]]+;q[++j]=t[k];
        } 
    fo(j,,) fo(i,,n) g[i][j]=g[g[i][j-]][j-],
    f[i][j]=max(f[i][j-],f[g[i][j-]][j-]);
    fo(i,,cnt) {
        int id=ask[i];
        an[e[id].id]=ans+(ll)e[id].v;
        an[e[id].id]-=(ll)lca(e[id].x,e[id].y);
    }
    fo(i,,m) printf("%lld\n",an[i]);
}