題意：給定初始無(wú)邊的\(n\)個(gè)點(diǎn)無(wú)向圖及\(q\)個(gè)操作，包括連邊（邊權(quán)\(w\)，\(0 \leq w \leq 10\)）、刪邊和查詢(xún)兩點(diǎn)間權(quán)值最大值最小的路徑權(quán)值，\(n,q \leq 10^5\)且保證無(wú)重邊。思路： - **線段樹(shù)分治 + 可撤銷(xiāo)并查集**：因\(w\)小，建\(11\)個(gè)圖，分別包含\(w \leq k(k \in [0,10])\)的邊。對(duì)操作按時(shí)間排序后在時(shí)間軸上分治，用可撤銷(xiāo)并查集維護(hù)區(qū)間有效邊。每條邊有效區(qū)間在線段樹(shù)上用\(\log\)個(gè)節(jié)點(diǎn)表示，分治到節(jié)點(diǎn)時(shí)加入或撤銷(xiāo)邊。非葉子區(qū)間先加邊，遞歸處理左右子區(qū)間，再撤銷(xiāo)邊；葉子區(qū)間若為查詢(xún)則判斷兩點(diǎn)是否連通，時(shí)間復(fù)雜度\(O(Vq\log^2q)\) 。 - **LCT做法**：先離線預(yù)處理邊的刪除時(shí)刻，用LCT維護(hù)每個(gè)圖的生成樹(shù)及刪邊操作。添加邊時(shí)，若兩點(diǎn)已連通且新邊刪除時(shí)刻晚，貪心地找出兩點(diǎn)路徑上刪除時(shí)間最早的邊判斷是否替換，復(fù)雜度\(O(Vq \log q)\) 。

P7457 [CERC2018] The Bridge on the River Kawaii

題意

給你一個(gè) \(n\) 個(gè)點(diǎn)初始沒(méi)有邊的無(wú)向圖。有 \(q\) 個(gè)操作。

1. 連邊 \((u,v)\)。權(quán)值為 \(w\)。
2. 刪邊 \((u,v)\)。
3. 查詢(xún) \(u,v\) 之間邊權(quán)最大值最小的路徑的最大邊權(quán)。

\(n,q \le 10^5, 0 \le w \le 10\)。

保證任意時(shí)刻沒(méi)有重邊。

思路

發(fā)現(xiàn) \(w\) 很小。所以把 \(w \le k(k \in [0,10])\) 的邊建成一個(gè)圖，建 \(11\) 個(gè)圖。

維護(hù)這些圖，每次查詢(xún)就在每個(gè)圖上都查一下。

---

對(duì)于一個(gè)圖，我們需要知道任意兩點(diǎn)是否連通。可以使用并查集維護(hù)。

但是有刪邊怎么辦？可以使用可撤銷(xiāo)并查集。

我們有套路的線段樹(shù)分治 + 可撤銷(xiāo)并查集做法。\(O(Vq\log^2q)\)。

我們把詢(xún)問(wèn)按照時(shí)間排序，然后分治處理。

為了保證分治復(fù)雜度正確，我們其實(shí)是在時(shí)間軸上分治，而不是在詢(xún)問(wèn)序列上分治。這樣可以保證分治區(qū)間的操作個(gè)數(shù)。

對(duì)每個(gè)分治區(qū)間，我們用可撤銷(xiāo)并查集維護(hù)在這個(gè)區(qū)間內(nèi)一直有效的邊。

具體地，每條邊在一段區(qū)間內(nèi)有效。我們把這段區(qū)間在線段樹(shù)上用 \(\log\) 個(gè)節(jié)點(diǎn)表示（類(lèi)似線段樹(shù)區(qū)間操作那樣）。

當(dāng)我們分治到這些節(jié)點(diǎn)時(shí)，就往并查集里加入這條邊。當(dāng)我們從這個(gè)節(jié)點(diǎn)回溯時(shí)，就從并查集撤銷(xiāo)這條邊。

對(duì)于非葉子分治區(qū)間 \([l,r]\)。

1. 往可撤銷(xiāo)并查集里加入一些邊。
2. 遞歸左半?yún)^(qū)間和右半?yún)^(qū)間。
3. 撤銷(xiāo)剛剛加入的邊。

對(duì)于葉子，如果這個(gè)葉子時(shí)查詢(xún)，就可以查詢(xún)一下 \(u,v\) 是否連通。

時(shí)間復(fù)雜度 \(O(Vq \log^2 q)\)。

常數(shù)不太大，能過(guò)。

---

還有 lct 做法。

我們先離線地預(yù)處理出每條邊的刪除時(shí)刻。

維護(hù)每個(gè)圖的生成樹(shù)。用 lct 維護(hù)刪邊操作。

還有個(gè)問(wèn)題，如果添加了一條新邊 \((u,v)\)，但是 \(u,v\) 已經(jīng)在一個(gè)連通塊里了。假如 \((u,v)\) 的刪除時(shí)刻比較晚，我們需要用 \((u,v)\) 代替樹(shù)上的某一條邊。

我們可以貪心地找出 \(u,v\) 之間的路徑的刪除時(shí)間最早的邊，并判斷是否換掉它。

這樣子復(fù)雜度就是 \(O(Vq \log q)\) 的。

但是我不會(huì) lct。

如有錯(cuò)請(qǐng)指出/bx

code

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace wing_heart {
	constexpr int N=1e5+7;
	int n,q;
	struct edge{
		int u,v,w,l,r;
	}e[N];
	struct pii {
		int u,v;
		bool operator < (const pii b) const { return u==b.u ? v<b.v : u<b.u; }
	}que[N];
	int ans[N];
	map<pii,int> mp;
	int ecnt;
	vector<int> vec[N<<2];
	void insert(int u,int l,int r,int x) {
		if(l>=e[x].l && r<=e[x].r) return vec[u].push_back(x);
		int mid=(l+r)>>1;
		if(e[x].l<=mid) insert(u<<1,l,mid,x);
		if(mid+1<=e[x].r) insert(u<<1|1,mid+1,r,x);
	}
	int fa[N],siz[N];
	stack<pii> st;
	int find(int x) { return !fa[x] ? x : find(fa[x]); }
	bool merge(int u,int v) {
		u=find(u), v=find(v);
		if(u==v) return 0;
		if(siz[u]<siz[v]) swap(u,v);
		siz[u]+=siz[v]; fa[v]=u;
		st.push({u,v});
		return 1;
	}
	void back() {
		int u=st.top().u, v=st.top().v;
		st.pop();
		siz[u]-=siz[v], fa[v]=0;
	}
	void solve(int u,int l,int r,int lim) {
		int cnt=0;
		for(int x : vec[u]) if(e[x].w<=lim) if(merge(e[x].u,e[x].v)) ++cnt;
		if(l==r) {
			if(que[l].u && find(que[l].u) == find(que[l].v)) ans[l] = lim;
		} else {
			int mid=(l+r)>>1;
			solve(u<<1,l,mid,lim), solve(u<<1|1,mid+1,r,lim);
		}
		rep(i,1,cnt) back();
	}
	void main() {
		sf("%d%d",&n,&q);
		rep(i,1,q) {
			int op,u,v;
			sf("%d%d%d",&op,&u,&v);
			if(u>v) swap(u,v);
			++u, ++v;
			if(op==0) {
				int w;
				sf("%d",&w);
				e[++ecnt] = {u,v,w,i,q};
				mp[{u,v}]=ecnt;
			} else if(op==1) {
				e[mp[{u,v}]].r=i-1;
			} else {
				ans[i]=-1;
				que[i]={u,v};
			}
		}
		rep(i,1,ecnt) insert(1,1,q,i);
		rep(i,1,n) siz[i]=1;
		per(i,10,0) {
			solve(1,1,q,i);
		}
		rep(i,1,q) if(que[i].u) pf("%d\n",ans[i]);
	}
}
int main() {
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("my.out","w",stdout);
	#endif
	wing_heart :: main();
}