【树链剖分+MST】CF609E

一时失言乱红尘 2024-03-22 22:32 81阅读 0赞

[Problem - E - Codeforces][]

题意：

![fbe0cef7c58548ce9f56c897e1888230.png][]

思路：

先把全局的MST求出来，然后对于一条边，如果它本来就在MST中，说明代价就是MST的权值和，否则它加入MST中，此时MST形成了环，我们把环中最大的那条边删掉，就相当于用这条边换掉了环中最大边，这样就是最小权值和

那么怎么求环中最大边，直接树剖即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=4e5+10;
    const int mxe=4e5+10;
    
    struct ty{
    	int to,next,w;
    }edge[mxe<<2];
    
    struct ty2{
    	int val,add;
    }tree[mxe<<2];
    
    struct ty3{
    	int u,v,w,id,Flag=0;
    }e[mxe<<2];
    
    int N,M,rt,P;
    int op,u,v,w;
    int tot=0,idx=0,answ=0;
    int F[mxn],ans[mxn],p[mxn];
    int head[mxn],sz[mxn],Fa[mxn],dep[mxn],id[mxn];
    int nw[mxn],son[mxn],top[mxn];
    
    void pushup(int rt){
    	tree[rt].val=max(tree[rt<<1].val,tree[rt<<1|1].val);
    }
    int query(int rt,int l,int r,int x,int y){
    	if(x<=l&&r<=y){
    		return tree[rt].val;
    	}
    	int mid=l+r>>1;
    	int res=0;
    	if(x<=mid) res=max(res,query(rt<<1,l,mid,x,y));
    	if(y>mid) res=max(res,query(rt<<1|1,mid+1,r,x,y));
    	return res;
    }
    int query_path(int u,int v){
    	int res=0;
    	while(top[u]!=top[v]){
    		if(dep[top[u]]<dep[top[v]]) swap(u,v);
    		res=max(res,query(1,1,N,id[top[u]],id[u]));
    		u=Fa[top[u]];
    	}
    	if(dep[u]>dep[v]) swap(u,v);
    	res=max(res,query(1,1,N,id[u]+1,id[v]));
    	return res;
    }
    void dfs2(int u,int t){
    	id[u]=++idx;
    	nw[idx]=p[u];
    	top[u]=t;
    	if(!son[u]) return;
    	dfs2(son[u],t);
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==Fa[u]||edge[i].to==son[u]) continue;
    		dfs2(edge[i].to,edge[i].to);
    	}
    }
    void dfs1(int u,int fa){
    	Fa[u]=fa;
    	dep[u]=dep[fa]+1;
    	sz[u]=1;
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa){
    			p[u]=edge[i].w;
    			continue;
    		}
    		dfs1(edge[i].to,u);
    		sz[u]+=sz[edge[i].to];
    		if(sz[son[u]]<sz[edge[i].to]) son[u]=edge[i].to;
    	}
    }
    void add(int u,int v,int w){
    	edge[tot].w=w;
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<mxn;i++){
    		head[i]=-1;
    	}
    }
    void build(int rt,int l,int r){
    	if(l==r){
    		tree[rt].val=nw[l];
    		return;
    	}
    	int mid=l+r>>1;
    	build(rt<<1,l,mid);
    	build(rt<<1|1,mid+1,r);
    	pushup(rt);
    }
    bool cmp(ty3 x,ty3 y){
    	return x.w<y.w;
    }
    int find(int x){
    	return F[x]=(x==F[x])?x:find(F[x]);
    }
    void join(int u,int v){
    	int f1=find(u),f2=find(v);
    	if(f1!=f2){
    		F[f1]=f2;
    	}
    }
    void solve(){
    	cin>>N>>M;
    	G_init();
    	for(int i=1;i<=N;i++) F[i]=i;
    	for(int i=1;i<=M;i++){
    		cin>>u>>v>>w;
    		e[i]={u,v,w,i,0};
    	}
    	sort(e+1,e+1+M,cmp);
    	for(int i=1;i<=M;i++){
    		if(find(e[i].u)==find(e[i].v)) continue;
    		join(e[i].u,e[i].v);
    		answ+=e[i].w;
    		e[i].Flag=1;
    		add(e[i].u,e[i].v,e[i].w);
    		add(e[i].v,e[i].u,e[i].w);
    	}
    	dfs1(1,0);
    	dfs2(1,0);
    	build(1,1,N);
    	for(int i=1;i<=M;i++){
    		ans[e[i].id]=answ+e[i].w-query_path(e[i].u,e[i].v);
    	}
    	for(int i=1;i<=M;i++) cout<<ans[i]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/609/problem/E
[fbe0cef7c58548ce9f56c897e1888230.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/fc4a3a7aacfa437e887256d31fe15bb2.png