[wc2006] director of water management

Dynamic maintenance of minimum spanning tree

link ：P4172 [WC2006] The water chief - Luogu | New ecology of computer science education (luogu.com.cn)

The question ： Given a simple undirected graph , Edges have weights , Ask or modify many times . Query is a query from u Point to v The minimum of all paths of a point , The value of the path is the maximum value of all edges passing through the path . Modification is to break an edge . The number of modifications shall not exceed $5\ast 10^3$.

Answer key ： First observe and ask this operation , It is found that when the minimum spanning tree is used , The path distance between any two points will be the smallest . Then the problem is to dynamically maintain a minimum spanning tree , It's obvious to use LCT To maintain the . Consider deleting edges , After deleting an edge , If it is the minimum spanning tree, then it is separated , It is necessary to find a minimal insertion in the edge set of an undirected graph that can connect two connected blocks , The complexity of traversing the edge set is too high . Turn over all query modifications , No change in query operation , But the operation of deleting edges is changed to that of adding edges , Just maintain each splay The edge with the largest edge weight in , When adding edges, compare whether the maximum edge weight on the chain is greater than the added edge weight , If yes, delete the largest edge , Join current edge ; If not, skip . Complexity $O(n\log n)$.
Be careful ： When maintaining the edge weight, convert the edge to a point .

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
const int maxn=2e5+5;

int n,m,q,x,y,z,w;
int f[maxn],c[maxn][2],v[maxn],s[maxn],mx[maxn],st[maxn];
int ans[maxn],id[1005][1005];
bool r[maxn];
#define lc c[x][0]
#define rc c[x][1]
struct node{
    
	int u,v,w,ex;
	inline bool operator<(const node&x)const{
    
		return w<x.w;
	}
}ed[maxn];
struct qy{
    
	int op,u,v;
}t[maxn];

bool nroot(int x)
{
    
	return c[f[x]][0]==x||c[f[x]][1]==x;
}

void pushup(int x)
{
    
	if(s[lc]<s[rc])s[x]=s[rc],mx[x]=mx[rc];
	else s[x]=s[lc],mx[x]=mx[lc];
	if(s[x]<v[x])s[x]=v[x],mx[x]=x;
}

void reverse(int x)
{
    
	swap(lc,rc),r[x]^=1;
}

void pushdown(int x)
{
    
	if(r[x])
	{
    
		if(lc)reverse(lc);
		if(rc)reverse(rc);
		r[x]=0;
	}
}

void rotate(int x)
{
    
	int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
	if(nroot(y))c[z][c[z][1]==y]=x;
	c[y][k]=w,c[x][!k]=y;
	if(w)f[w]=y; f[y]=x,f[x]=z;
	pushup(y);
}

void splay(int x)
{
    
	int y=x,z=0;
	st[++z]=y;
	while(nroot(y))st[++z]=y=f[y];
	while(z)pushdown(st[z--]);
	while(nroot(x))
	{
    
		y=f[x],z=f[y];
		if(nroot(y))
		{
    
			rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
		}
		rotate(x);
	}
	pushup(x);
}

void access(int x)
{
    
	for(int y=0;x;x=f[y=x])
	{
    
		splay(x),rc=y,pushup(x);
	}
}

void makeroot(int x)
{
    
	access(x),splay(x),reverse(x);
}

int findroot(int x)
{
    
	access(x),splay(x);
	while(lc)pushdown(x),x=lc;
	splay(x); return x;
}

void split(int x,int y)
{
    
	makeroot(x),access(y),splay(y);
}

bool link(int x,int y,int o)
{
    
	makeroot(x);
	if(findroot(y)!=x){
    if(o)f[x]=y; return true;}
	return false;
}

bool cut(int x,int y)
{
    
	makeroot(x);
	if(findroot(y)==x&&f[y]==x&&!c[y][0])
	{
    
		f[y]=c[x][1]=0; pushup(x); return true;
	}
	return false;
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>q;
	for(int i=n+1;i<=n+m;i++)
	{
    
		cin>>ed[i].u>>ed[i].v>>ed[i].w; 
	}
	sort(ed+n+1,ed+n+1+m); 
	for(int i=n+1;i<=n+m;i++)
	{
    
		id[ed[i].u][ed[i].v]=id[ed[i].v][ed[i].u]=i;
		v[i]=ed[i].w;
	}	
	for(int i=1;i<=q;i++)
	{
    
		cin>>t[i].op>>t[i].u>>t[i].v;
		if(t[i].op==2)ed[id[t[i].u][t[i].v]].ex=1;
	}
	int cnt=0;
	for(int i=n+1;i<=n+m;i++)
	{
    
		if(cnt<n-1&&!ed[i].ex&&link(ed[i].u,ed[i].v,0))
		{
    
			link(ed[i].u,i,1),link(ed[i].v,i,1),cnt++;
		}
	}
	for(int i=q;i>=1;i--)
	{
    
		if(t[i].op==1)
		{
    
			split(t[i].u,t[i].v),ans[i]=s[t[i].v];
		}
		else
		{
    
			int d=id[t[i].u][t[i].v];
			split(t[i].u,t[i].v);
			if(s[t[i].v]>ed[d].w)
			{
    
				int d2=mx[t[i].v];
				cut(ed[d2].u,d2),cut(ed[d2].v,d2);
				link(t[i].u,d,1),link(t[i].v,d,1);
			}
		}
	}
	for(int i=1;i<=q;i++)
	{
    
		if(t[i].op==1)cout<<ans[i]<<"\n";
	}
	return 0;
}