树剖线段树为何30

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ls rt<<1
#define rs rt<<1|1
#define mid ((l+r)>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
using namespace std;
const int N = 1e5 + 10;
const ll INF = 1e10;
template<typename TY>
inline void read(TY &s){
	ll x = 0, f = 1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar(); 
	}
	s = x * f;
}
struct edge{
	int u,v; ll w; int k2,id;
	edge(int a=0,int b=0,ll c=0){
		u=a,v=b,w=c;
	}
	bool operator<(const edge &o) const{return k2==o.k2 ? w < o.w : k2 < o.k2;}
}E[N];
vector<edge> e[N];
int n,m,f[N],cnt;
ll sum;
int find(int x){
	if(f[x] != x) f[x] = find(f[x]);
	return f[x];
}
int fa[N],son[N],deep[N],top[N],siz[N],dfn[N],pos[N],tim;
void dfs1(int u){
//	cerr<<u<<"u\n";
	deep[u] = deep[fa[u]] + 1; siz[u] = 1;
	for(auto x : e[u]){
		if(x.v == fa[u]) continue;
		fa[x.v] = u; dfs1(x.v);
		siz[u] += siz[x.v];
		if(!son[u]||siz[son[u]] < siz[x.v]) son[u] = x.v;
	}
}
void dfs2(int u,int topx){
	top[u] = topx;
	dfn[u] = ++tim; pos[tim] = u;
	if(son[u]) dfs2(son[u],topx);
	for(auto x : e[u]){
		if(x.v == fa[u] || x.v == son[u]) continue;
		dfs2(x.v,x.v);
	}
}
int c[N<<2],tag[N<<2],ans[N];
inline void push_down(int rt,int l,int r){
	if(tag[rt]){
		c[ls] = c[rs] = tag[ls] = tag[rs] = tag[rt];
		tag[rt] = 0;
	}
}
void modify(int rt,int l,int r,int ql,int qr,int v){
//	cerr << rt << "rt ->";
	if(tag[rt]||c[rt]) return;
	if(ql <= l && r <= qr){
//		cerr<<pos[l] << " " << pos[r] << "pos\n";
		c[rt] = tag[rt] = v;
		return;
	}
	push_down(rt,l,r);
	if(ql <= mid) modify(lson,ql,qr,v);
	if(mid + 1 <= qr) modify(rson,ql,qr,v);
}
ll query(int rt,int l,int r,int x){
	if(l == r) return c[rt];
	push_down(rt,l,r);
	if(x <= mid) return query(lson,x);
	else return query(rson,x);
}
inline void change(int x,int y,int v){
//	cerr<<"change into\n";
	while(top[x]!=top[y]){
		if(deep[top[x]] < deep[top[y]]) swap(x,y);
		modify(1,1,n,dfn[top[x]],dfn[x],v);
		x = fa[top[x]];
	}
	if(x == y) return;
	if(deep[x] > deep[y]) swap(x,y);
	modify(1,1,n,dfn[x]+1,dfn[y],v);
//	cerr << "change out\n";
}
signed main(){
	read(n); read(m);
	for(int i=1;i<=m;i++){
		read(E[i].u); read(E[i].v); read(E[i].w); 
		E[i].id = i; E[i].k2 = 0;
	}
	for(int i=1;i<=n;i++) f[i] = i;
	sort(E+1,E+m+1);
	for(int i=1;i<=m;i++){
		int u = find(E[i].u), v = find(E[i].v);
		if(u == v) continue;
		f[v] = u;
		sum += E[i].w; E[i].k2 = 1;
		e[E[i].u].push_back(edge(E[i].u,E[i].v,E[i].w));
		e[E[i].v].push_back(edge(E[i].v,E[i].u,E[i].w)); 
		if(++cnt >= n-1) break;
	}
	dfs1(1); dfs2(1,1);
	sort(E+1,E+m+1);
	for(int i=1;i<=m;i++){
		if(E[i].k2) break;
		int u = E[i].u , v = E[i].v;
//		cerr<<u<<" "<<v<<"?????\n";
		change(u,v,E[i].w);
	}
	for(int i=1;i<=m;i++){
		int u = E[i].u , v = E[i].v;
		if(!E[i].k2){
			ans[E[i].id] = sum;
			continue;
		}
		if(deep[u] > deep[v]) swap(u,v);
		int k = query(1,1,n,dfn[v]);
		ans[E[i].id] =  k ? sum - E[i].w + k : -1;
	}
	for(int i=1;i<=m;i++){
		cout << ans[i] << "\n";
	}
	return 0;
}