题解：P14080 [GESP202509 八级] 最小生成树
这是 GESP？？？
在机房走之前看到了这个题，路上思考 10min 无果，回家手玩样例发现我糖丸了。
首先求出最小生成树，之后我们发现，每删一条边就是将原树分为两个不同的联通快，你需要在这两个联通块的其余点对间找一条最短非树边加上。
发现正着做不好维护，考虑反过来。
我们发现，对于一条非树边，它会对该边两个端点之间的树上路径产生贡献，即若删除这两个点树上路径的任意一边，都可以用该边替代，证明显然。
所以将每一条非树边的权值丢进线段树跑树剖，之后对于每一条树边，求出路径上最小值，一加一减即为答案。
注意这里是边权，所以要将边权转成点权，把每条边的权值下放到他的靠下的端点即可，详情见 P4315。
代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int l,r,add,mi;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define add(x) tree[x].add
#define mi(x) tree[x].mi
}tree[1000005];
int res,n,m,x,y,k,a[1000005],root,MOD,tim,w[1000005],fat[1000005],cnt,val[1000005];
bool flag[1000005];
int dep[1000005];//深度
int id[1000005];//所在重链编号
int fa[1000005];//父节点编号
int siz[1000005];//子树大小
int heavy[1000005];//重儿子编号
int dfn[1000005];//dfs序
vector<int>vec[1000005];
void dfs(int p,int d,int fat)
{
fa[p]=fat,dep[p]=d,siz[p]=1;
for(auto it:vec[p])
{
if(it==fat) continue;
dfs(it,d+1,p);
siz[p]+=siz[it];
if(siz[heavy[p]]<siz[it]) heavy[p]=it;
}
}
void dfs1(int p,int start,int fat)
{
dfn[p]=(++tim),id[p]=start,w[tim]=a[p];
if(!heavy[p]) return ;
dfs1(heavy[p],start,p);
for(auto it:vec[p])
{
if(it==heavy[p]||it==fat) continue;
dfs1(it,it,p);
}
}
void build(int p,int l,int r)
{
l(p)=l,r(p)=r,mi(p)=add(p)=9e18;
if(l==r) return ;
int mid=l+r>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
void spread(int p)
{
if(add(p)!=9e18)
{
add(p*2)=min(add(p*2),add(p));
add(p*2+1)=min(add(p*2+1),add(p));
mi(p*2)=min(mi(p*2),add(p));
mi(p*2+1)=min(mi(p*2+1),add(p));
add(p)=9e18;
}
}
void change(int p,int l,int r,int d)
{
if(l<=l(p)&&r(p)<=r)
{
mi(p)=min(mi(p),d);
add(p)=min(add(p),d);
return ;
}
spread(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid) change(p*2,l,r,d);
if(r>mid) change(p*2+1,l,r,d);
mi(p)=min(mi(p*2),mi(p*2+1));
}
int ask(int p,int l,int r)
{
if(l<=l(p)&&r(p)<=r) return mi(p);
spread(p);
int mid=(l(p)+r(p))>>1;
int ans=9e18;
if(l<=mid) ans=min(ans,ask(p*2,l,r));
if(mid<r) ans=min(ans,ask(p*2+1,l,r));
return ans;
}
void tree_change(int l,int r,int k)
{
//钦定l的重链的起始点深度更大
while(id[l]!=id[r])
{
if(dep[id[l]]<dep[id[r]]) swap(l,r);
change(1,dfn[id[l]],dfn[l],k);
l=fa[id[l]];
}
if(dep[l]<dep[r]) swap(l,r);
change(1,dfn[r]+1,dfn[l],k);
}
struct node1{
int to,next,w,id;
}t[1000005];
bool cmp(node1 a,node1 b)
{
return a.w<b.w;
}
int find(int i)
{
if(i==fat[i]) return i;
return fat[i]=find(fat[i]);
}
int kruscal()
{
int ans=0,cnt1=0;
for(int i=1;i<=cnt;i++)
{
int x=find(t[i].to),y=find(t[i].next);
if(x!=y)
{
flag[i]=1;
fat[x]=y;
vec[t[i].to].push_back(t[i].next);
vec[t[i].next].push_back(t[i].to);
ans+=t[i].w;
cnt1++;
}
}
if(cnt1==n-1) return ans;
return -1;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) fat[i]=i;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
t[++cnt]={u,v,w,i};
}
sort(t+1,t+cnt+1,cmp);
res=kruscal();
dfs(1,1,0);dfs1(1,1,0);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int pos=t[i].id;
if(flag[i]) continue;
tree_change(t[i].to,t[i].next,t[i].w);
}
for(int i=1;i<=m;i++)
{
int pos=t[i].id;
if(!flag[i]){val[pos]=res;continue;}
int x;
if(dep[t[i].to]>dep[t[i].next]) x=t[i].to;
else x=t[i].next;
int mi=ask(1,dfn[x],dfn[x]);
if(mi==9e18){val[pos]=-1;continue;};
val[pos]=res+mi-t[i].w;
}
for(int i=1;i<=m;i++) cout<<val[i]<<"\n";
return 0;
}