题解：P14080 [GESP202509 八级] 最小生成树

#include<bits/stdc++.h>

#define pii pair<int,int> 
#define pll pair<long long,long long> 
#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define in4(a,b,c,d) a=read(), b=read(), c=read(), d=read()
#define fst first 
#define scd second 
#define dbg puts("IAKIOI")

using namespace std;

int read() {
	int x=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
	for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

#define maxn 200050

int n,m;
struct edge{
	int u,v,d,idx;
	bool operator<(const edge &x) const {
		return d<x.d;
	}
}ed[maxn];
bool vis[maxn];
vector<int> G[maxn];
struct Dsu {
	int fa[maxn];
	void pre(int n) {
		For(i,1,n) fa[i]=i;
	}
	int fnd(int x) {return fa[x]==x?fa[x]:fa[x]=fnd(fa[x]); }
	void uni(int x,int y) {
		fa[fnd(x)]=fnd(y);
	}
}dsu;

struct node {
	int dep,fa,siz,mxs;
	int dfn,top;
}tr[maxn]; int dfntop;

void dfs1(int u,int fa) {
	tr[u].fa=fa,tr[u].dep=tr[fa].dep+1;
	tr[u].siz=1;
	for(auto v:G[u]) if(v!=fa) {
		dfs1(v,u);
		tr[u].siz+=tr[v].siz;
		if(tr[v].siz>tr[tr[u].mxs].siz) tr[u].mxs=v;
	}
}
void dfs2(int u,int Ltop) {
	tr[u].dfn=++dfntop; tr[u].top=Ltop;
	if(tr[u].mxs) dfs2(tr[u].mxs,Ltop);
	for(auto v:G[u]) if(v!=tr[u].fa&&v!=tr[u].mxs) dfs2(v,v);
}

struct SegT {
	struct Tnode {
		int mn,tag;
	}tr[maxn<<2];
	void psu(int idx) {
		tr[idx].mn=min(tr[lc(idx)].mn,tr[rc(idx)].mn);
	}
	void psd(int idx,int l,int r) {
		if(tr[idx].tag==1e9) return ;
		tr[lc(idx)].mn=min(tr[lc(idx)].mn,tr[idx].tag);
		tr[rc(idx)].mn=min(tr[rc(idx)].mn,tr[idx].tag);
		tr[lc(idx)].tag=min(tr[lc(idx)].tag,tr[idx].tag);
		tr[rc(idx)].tag=min(tr[rc(idx)].tag,tr[idx].tag);
		tr[idx].tag=1e9;
	}
	void build(int idx,int l,int r) {
		tr[idx].mn=tr[idx].tag=1e9;
		if(l==r) return ;
		int mid=l+r>>1;
		build(lc(idx),l,mid);
		build(rc(idx),mid+1,r);
		psu(idx);
	}
	void modi(int idx,int l,int r,int L,int R,int val) {
		if(L<=l&&r<=R) {
			tr[idx].mn=min(tr[idx].mn,val);
			tr[idx].tag=min(tr[idx].tag,val);
			return;
		}
		psd(idx,l,r);
		int mid=l+r>>1;
		if(L<=mid) modi(lc(idx),l,mid,L,R,val);
		if(R>mid) modi(rc(idx),mid+1,r,L,R,val);
		psu(idx);
	}
	int query(int idx,int l,int r,int L,int R) {
		if(L<=l&&r<=R) return tr[idx].mn;
		int mid=l+r>>1,res=1e9; psd(idx,l,r);
		if(L<=mid) res=query(lc(idx),l,mid,L,R);
		if(R>mid) res=min(res,query(rc(idx),mid+1,r,L,R));
		return res;
	}
}Tr;

void add(int u,int v,int c) {
	while(tr[u].top!=tr[v].top) {
		if(tr[tr[u].top].dep<tr[tr[v].top].dep) swap(u,v);
		Tr.modi(1,1,n,tr[tr[u].top].dfn,tr[u].dfn,c);
		u=tr[tr[u].top].fa;
	}
	if(tr[u].dep>tr[v].dep) swap(u,v);
	if(tr[u].dep<tr[v].dep) Tr.modi(1,1,n,tr[u].dfn+1,tr[v].dfn,c);
}

int query(int u,int v) {
	int res=1e9;
	while(tr[u].top!=tr[v].top) {
		if(tr[tr[u].top].dep<tr[tr[v].top].dep) swap(u,v);
		res=min(res,Tr.query(1,1,n,tr[tr[u].top].dfn,tr[u].dfn));
		u=tr[tr[u].top].fa;
	}
	if(tr[u].dep>tr[v].dep) swap(u,v);
	if(tr[u].dep<tr[v].dep) res=min(res,Tr.query(1,1,n,tr[u].dfn+1,tr[v].dfn));
	return res;
}

ll totans[maxn];

void work() {
	in2(n,m);
	For(i,1,m) {
		in3(ed[i].u,ed[i].v,ed[i].d);
		ed[i].idx=i;
	}
	sort(ed+1,ed+m+1);
	dsu.pre(n);
	ll ans=0;
	For(i,1,m) {
		auto [u,v,d,idx]=ed[i];
		if(dsu.fnd(u)!=dsu.fnd(v)) {
			G[u].push_back(v);
			G[v].push_back(u);
			dsu.uni(u,v); ans+=d; vis[i]=1;
		}
	}
	dfs1(1,0);dfs2(1,1);
	Tr.build(1,1,n);
	For(i,1,m) if(!vis[i]){
		add(ed[i].u,ed[i].v,ed[i].d);
	}
	For(i,1,m) {
		if(!vis[i]) {
			totans[ed[i].idx]=ans;
		} else {
			int res=query(ed[i].u,ed[i].v);
			totans[ed[i].idx]=ans-ed[i].d+res;
			if(res==1e9) totans[ed[i].idx]=-1;
		}
	}
	For(i,1,m) cout<<totans[i]<<'\n';
}

signed main() {
//	freopen("data.in","r",stdin);
//	freopen("myans.out","w",stdout);
//	ios::sync_with_stdio(false); 
//	cin.tie(0); cout.tie(0);
	double stt=clock();
	int _=1;
//	_=read();
//	cin>>_;
	For(i,1,_) {
		work();
	}
	cerr<<"\nTotal Time is:"<<(clock()-stt)*1.0/1000<<" second(s)."<<'\n';
	return 0;
}