题解：P14080 [GESP202509 八级] 最小生成树
感谢洛谷管理员的积极审核
题目链接
题目大意
题目说的很直白，那么我们就开始想解法。
暴力
肯定是可以的，就是每次删边后重新跑一遍最小生成树，然而这是肯定会超时的。
正解
一想到一道题目的内容包括了最小生成树和删边，那我们不难想到使用克鲁斯卡尔重构树套上重链剖分（不会的看这里）。
具体思路是这样的：我们考虑在重构树上进行树剖，但是每条边的边权初始化都是无穷大。我们的操作是：我们只在图上的每一条不是树边的边，我们对于它连接的两点在最小生成树上的路径的权值进行覆盖，线段树负责记录最小值。
这个意思是：我们的树剖负责记录每条非树边的贡献。
你可以这样想：毕竟要删的边只分两种（树边和非树边），非树边删了不会对原先的最小生成树产生影响，而树边删了之后要用最小的连接性的非树边替换，这个用树链剖分维护就行了。
替换的话要在所有的非树边都计算贡献后再算。
那就解完了
AC Code
#include<bits/stdc++.h>
#define int long long
#define bug cout<<"BUG\n"
#define V vector
using namespace std;
const int N=2e5+10;
const int INF=1e18+10;
struct SegTree{
struct node{
int l,r,tag,minn;
};
V<node>a;
SegTree(int _n):a(_n*4+2){}
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
void push_up(int x){
a[x].minn=min(a[ls(x)].minn,a[rs(x)].minn);
}
void addtag(int x,int w){
a[x].tag=min(a[x].tag,w);
a[x].minn=min(a[x].minn,w);
}
void push_down(int x){
if(a[x].tag!=INF){
addtag(ls(x),a[x].tag);
addtag(rs(x),a[x].tag);
a[x].tag=INF;
}
}
void build(int x,int l,int r){
a[x].l=l;a[x].r=r;a[x].tag=INF;
if(l==r){
a[x].minn=INF;
return;
}
int mid=l+r>>1;
build(ls(x),l,mid);build(rs(x),mid+1,r);
push_up(x);
}
void update(int x,int L,int R,int w){
if(a[x].l>=L&&a[x].r<=R){
addtag(x,w);
return;
}
push_down(x);
int mid=a[x].l+a[x].r>>1;
if(L<=mid) update(ls(x),L,R,w);
if(R>mid) update(rs(x),L,R,w);
push_up(x);
}
int query(int x,int L,int R){
if(a[x].l>=L&&a[x].r<=R) return a[x].minn;
push_down(x);
int res=INF,mid=(a[x].l+a[x].r)>>1;
if(L<=mid) res=min(res,query(ls(x),L,R));
if(R>mid) res=min(res,query(rs(x),L,R));
return res;
}
};
\\树链剖分
using P=array<int,2>;
using T=array<int,4>;
using LLS=array<int,3>;
V<V<P> >e;
V<LLS>edge;
V<int>val,former,siz,son,id,top,dep,fa;
void dfs1(int u,int fat){
fa[u]=fat;
dep[u]=dep[fat]+1;
siz[u]=1;
for(auto i:e[u]){
int v=i[0],w=i[1];
if(v==fat)continue;
dfs1(v,u);
former[v]=w;
siz[u]+=siz[v];
if(!son[u]||siz[son[u]]<siz[v]) son[u]=v;
}
}
int cnt=0;
void dfs2(int u,int tp){
top[u]=tp;
id[u]=++cnt;
if(!son[u])return;
dfs2(son[u],tp);
for(auto i:e[u]){
int v=i[0];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
void update(SegTree &lls,int u,int v,int w){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
lls.update(1,id[top[u]],id[u],w);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
if(u!=v) lls.update(1,id[son[u]],id[v],w);
}
int query(SegTree &lls,int u,int v){
int ans=INF;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
ans=min(ans,lls.query(1,id[top[u]],id[u]));
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
if(u!=v) ans=min(ans,lls.query(1,id[son[u]],id[v]));
return ans;
}
int fin(int x){
if(fa[x]!=x) fa[x]=fin(fa[x]);
return fa[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;cin>>n>>m;
V<T>ee(m+1);
V<int>du(n+1,0);
e.resize(n+1);val.resize(n+1);former.resize(n+1);
top.resize(n+1);dep.resize(n+1);id.resize(n+1);
fa.resize(n+1);siz.resize(n+1);son.resize(n+1);
edge.resize(m+1);
for(int i=1;i<=m;i++){
cin>>ee[i][1]>>ee[i][2]>>ee[i][0];ee[i][3]=i;
edge[i]={ee[i][1],ee[i][2],ee[i][0]};
}
map<int,bool>mp;
for(int i=1;i<=n;i++)fa[i]=i;
sort(ee.begin()+1,ee.end());
int tot=0,ans=0;
for(int i=1;i<=m;i++){\\最小生成树
int u=ee[i][1],v=ee[i][2],w=ee[i][0],id=ee[i][3];
if(fin(u)!=fin(v)){
fa[fin(u)]=fin(v);
e[u].push_back({v,w});
e[v].push_back({u,w});
ans+=w;
mp[id]=true;
tot++;
}
if(tot==n-1)break;
}
for(int i=1;i<=n;i++){
if(!dep[i]){
dfs1(i,0);dfs2(i,i);
}
}
SegTree lls(n+1);
lls.build(1,1,n);
V<int>tr_ans(m+1,0);
for(int i=1;i<=m;i++){
int u=edge[i][0],v=edge[i][1],w=edge[i][2];
if(!mp.count(i)){
// cout<<"---Not Tree Edge u:"<<u<<" v:"<<v<<"\n";
update(lls,u,v,w);
}
}
for(int i=1;i<=m;i++){
// cout<<"--u:"<<edge[i][0]<<" v:"<<edge[i][1]<<" w:"<<edge[i][2]<<"\n";
if(!mp.count(i)) cout<<ans<<"\n";
else{
int anss=query(lls,edge[i][0],edge[i][1]);
// cout<<"---i="<<i<<" "<<anss<<"\n";
if(anss>=INF) cout<<"-1\n";
else cout<<ans-edge[i][2]+anss<<"\n";
}
}
return 0;
}