LCT维护MST

以MST的模板为例：

题目链接：MST模板

LCT维护MST一般是，图存在加边的动态MST，如果是删边，那么我们可以考虑使用时间倒流实现把删边变加边。但是如果是即加边又删边就不行了。

对于加边时，如果此两点没有连通，肯定是直接连接。但是如果连接了呢？,，我们就需要用当前的边来替换路径的最大值。然后我们还需要维护当前路径最大边的编号，方便cut断边。

LCT维护的点权，但是我们需要边权，所以我们可以用点来表示边。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=3e5+10;
int n,m,idx,w[N],res;
int cnt,st[N];
struct node{int ch[2],fa,mx,id,re;}t[N];
inline void push_up(int p){
	t[p].id=p,t[p].mx=w[p];
	if(t[t[p].ch[0]].mx>t[p].mx) t[p].id=t[t[p].ch[0]].id,t[p].mx=t[t[p].ch[0]].mx;
	if(t[t[p].ch[1]].mx>t[p].mx) t[p].id=t[t[p].ch[1]].id,t[p].mx=t[t[p].ch[1]].mx;
}
inline void push_re(int p){swap(t[p].ch[0],t[p].ch[1]); t[p].re^=1;}
inline void push_down(int p){
	if(t[p].re){
		if(t[p].ch[0])	push_re(t[p].ch[0]);
		if(t[p].ch[1])	push_re(t[p].ch[1]); t[p].re^=1;
	}
}
inline bool isroot(int x){return t[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;}
inline void rotate(int x){
	int y=t[x].fa,z=t[y].fa,k=t[y].ch[1]==x,w=t[x].ch[!k];
	if(!isroot(y))	t[z].ch[t[z].ch[1]==y]=x; t[x].ch[!k]=y; t[y].ch[k]=w;
	if(w)	t[w].fa=y; t[y].fa=x; t[x].fa=z;	push_up(y);
}
inline void splay(int x){
	cnt=1;	st[cnt]=x; int y=x;
	while(!isroot(y))	st[++cnt]=y=t[y].fa;
	while(cnt)	push_down(st[cnt--]);
	while(!isroot(x)){
		int y=t[x].fa,z=t[y].fa;
		if(!isroot(y))	rotate((t[y].ch[0]==x)^(t[z].ch[0]==y)?x:y); rotate(x);
	}push_up(x);
}
inline void access(int x){
	for(int y=0;x;x=t[y=x].fa) splay(x),t[x].ch[1]=y,push_up(x); 
}
inline void makeroot(int x){
	access(x); splay(x); push_re(x);
}
inline int find(int x){
	access(x); splay(x); while(t[x].ch[0]) push_down(x),x=t[x].ch[0]; 
	splay(x);	return x;
}
inline void split(int x,int y){
	makeroot(x); access(y); splay(y);
}
inline void link(int x,int y){
	makeroot(x); 	if(find(y)!=x)	t[x].fa=y;
}
inline void cut(int x,int y){
	makeroot(x); 
	if(find(y)==x&&t[y].fa==x&&!t[y].ch[0]) t[y].fa=t[x].ch[1]=0,push_up(x);
}
signed main(){
	cin>>n>>m;	idx=n;
	for(int i=1,a,b,c;i<=m;i++){
		scanf("%d %d %d",&a,&b,&c);
		w[++idx]=c;	makeroot(a);
		if(find(b)!=a){
			link(a,idx);	link(idx,b);	res+=c;	continue;
		}
		split(a,b);	int now=t[b].id;
		if(t[now].mx<=c)	continue;
		res+=(c-t[now].mx),splay(now);
		t[t[now].ch[0]].fa=t[t[now].ch[1]].fa=0;
		link(a,idx),link(idx,b); 
	}
	cout<<res<<endl;
	return 0;
}