You can make a normal version first \ (> \) Director of water management

Description

For a graph with n points and m edges, the following operations are supported:

• Query the minimum value of the maximum edge weight on the path among all paths from \ (x \) to \ (y \);
• Delete an edge;

Solution

The basic idea is similar to the ordinary version.

Because it is difficult to delete edges, we choose to do the opposite and add edges.

Edge processing

• First, store all edges with structures. Because the data is strengthened, it is naturally unrealistic to store numbers with arrays. Only search can be used. Therefore, in order to facilitate the search, the size relationship between the two nodes should be handled well when entering;
• The edges are sorted according to the length first, which is convenient for the operation of converting the edges into points later;
• Then enter the number of the current edge when the edge is broken and make a mark;
• After the previous processing, connect the unmarked (not broken) edges for preprocessing.
• Finally, because it is added in reverse, the flashback is processed.

Tips: converting edges into points

In fact, the edge is regarded as a point and connected to two endpoints respectively.

That is, an edge \ ((x\) \(--\) \(y) \ (= > \) \ ((x \) \ (-- \) \ (Z \) \ (-- \) \ (y) \)

So the problem is to dynamically maintain the minimum spanning tree.

Because it is a spanning tree, each addition of edges must form a ring. And because we maintain the minimum spanning tree, we need to delete the largest edge in this ring. That is, when there is no edge, the maximum edge weight between the two endpoints is compared with the new edge weight, and the largest one is deleted.

Subsequent edging operation

Add the side of \ ((u,v) \).

• Find the maximum edge weight on the chain from \ (u \) to \ (v \);
• If the new edge weight is greater, do not do any operation;
• Otherwise, delete the original edge and add a new edge.

Query answer

The maximum value has been maintained during modification, so you can directly query the maximum value on the chain.

The following is the routine operation. Note that the number after the edge is converted into a point is \ (n + i \)~

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1500005;
#define il inline
#define ls ch[x][0]
#define rs ch[x][1]
il int read() {
	int x = 0; char s = getchar();
	while(s < '0' || s > '9') s = getchar();
	while(s <= '9' && s >= '0') x = x * 10 + s - '0', s = getchar();
	return x;  
}
bool tag[N];
int m,top,tot,fa[N],mx[N],val[N],ch[N][2],sta[N],fb[N];
struct node {int u,v,w,id; bool d;}e[N];
struct Query {int f,x,y,ans,id;}q[N];
il bool operator<(node a,node b) {
	return a.u < b.u || (a.u == b.u && a.v < b.v);
}
il bool cmp(node a,node b) {return a.w < b.w;}
il bool cmp2(node a,node b) {return a.id < b.id;}
il int getfa(int x) {return x == fb[x] ? x : fb[x] = getfa(fb[x]);}
il int find(int x,int y) {
	int l = 1, r = m, mid;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(e[mid].u < x || (e[mid].u == x && e[mid].v < y)) l = mid + 1;
		else if(e[mid].u == x && e[mid].v == y) return mid;
		else r = mid - 1;
	}
}
il bool check(int x) {
	return ch[fa[x]][0] != x && ch[fa[x]][1] != x; 
}
il void update(int x) {
	mx[x] = x;
	if(val[mx[ls]] > val[x]) mx[x] = mx[ls];
	if(val[mx[rs]] > val[mx[x]]) mx[x] = mx[rs]; 
}
il int ident(int x) {
	return ch[fa[x]][1] == x;
}
il void rotate(int x) {
	int f = fa[x], ff = fa[f], k = ident(x);
	if(!check(f)) ch[ff][ident(f)] = x;
	fa[x] = ff, fa[f] = x, fa[ch[x][k ^ 1]] = f;
	ch[f][k] = ch[x][k ^ 1], ch[x][k ^ 1] = f;
	update(f), update(x);
}
il void pushdown(int x) {
	if(tag[x]) {
		tag[x] = 0, tag[ls] ^= 1, tag[rs] ^= 1;
		swap(ls,rs);
	}
}
il void splay(int x) {
	sta[top = 1] = x;
	int y = x, f, ff;
	while(!check(y)) sta[++top] = fa[y], y = fa[y];
	while(top) pushdown(sta[top--]);
	while(!check(x)) {
		f = fa[x];
		if(!check(f)) ident(x) ^ ident(f) ? rotate(x) : rotate(f);
		rotate(x);
	}
}
il void access(int x) {
	for(register int y = 0; x; x = fa[y = x]) {
		splay(x), rs = y, update(x);
	}
}
il void makert(int x) {
	access(x), splay(x), tag[x] ^= 1;
}
il void link(int x,int y) {
	makert(x), fa[x] = y;
}
il void cut(int x,int y) {
	makert(x), access(y), splay(y);
	fa[x] = ch[y][0] = 0;
}
il int query(int x,int y) {
	makert(x), access(y), splay(y);
	return mx[y];
}
int main() {
	int i,n,qq,u,v,x,y,k,t;
	n = read(), m = read(), qq = read();
	for(i = 1; i <= n; i ++) fb[i] = i;
	for(i = 1; i <= m; i ++) {
		e[i].u = read(), e[i].v = read(), e[i].w = read();
		if(e[i].u > e[i].v) swap(e[i].u, e[i].v);
	}
	sort(e + 1, e + 1 + m, cmp);
	for(i = 1; i <= m; i ++) {
		e[i].id = i, val[n + i] = e[i].w, mx[n + i] = n + i;
	}
	sort(e + 1,e + m + 1);
	for(i = 1; i <= qq; i ++) {
		q[i].f = read(), q[i].x = read(), q[i].y = read();
		if(q[i].f == 2) {
			if(q[i].x > q[i].y) swap(q[i].x,q[i].y);
			int t = find(q[i].x,q[i].y);
			e[t].d = 1, q[i].id = e[t].id;
		}
	}
	sort(e + 1,e + 1 + m,cmp2);
	for(i = 1; i <= m; i ++) {
		if(!e[i].d) {
			u = e[i].u, v = e[i].v, x = getfa(u), y = getfa(v);
			if(x != y) {
				fb[x] = y;
				link(u,i + n), link(v,i + n), tot++;
				if(tot == n - 1) break;
			}
		}
	}
	for(i = qq; i; i --) {
		if(q[i].f == 1) q[i].ans = val[query(q[i].x,q[i].y)];
		else {
			u = q[i].x, v = q[i].y, k = q[i].id, t = query(u,v);
			if(e[k].w < val[t]) {
				cut(e[t - n].u,t), cut(e[t - n].v,t);
				link(u,k + n), link(v,k +n);
			}
		}
	}
	for(i = 1; i <= qq; i ++) {
		if(q[i].f == 1) printf("%d\n",q[i].ans);
	}
	return 0;
}