一个较为简单的题目，做起来比较舒服。
题目
有 \(N\) 个点 \(M\) 条边。 有 \(Q\) 个询问，每个询问有 \(L,R\)。
询问 \(L\le a \le b \le R\) 最少需要前几条边才能联通。
都是 \(1e5\) 级别。
做法
我们把第 \(i\) 条边的边权设为 \(i\)，这就成为了一道 Kruskal 重构树的简单题。
我们简单可以处理 \(i\to i+1\) 的答案。
用线段树查询，代码如下
#include <bits/stdc++.h>
using namespace std;
const int MN=2e5+116;
int T, n, m, q;
struct Node{int nxt, to;
}node[MN<<1];
int head[MN<<1], tottt;
void insert(int u, int v){node[++tottt].to=v;node[tottt].nxt=head[u];head[u]=tottt; return;
}
struct Side{int u, v, w;bool operator <(const Side &o){return w<o.w;}
}side[MN];
int father[MN], cnttt, val[MN], lg[MN];
int find(int x){if(father[x]!=x) father[x]=find(father[x]);return father[x];
}
int jump[MN][20], depth[MN];
void dfs(int u, int father){depth[u]=depth[father]+1;jump[u][0]=father;for(int i=1; i<=19; ++i){jump[u][i]=jump[jump[u][i-1]][i-1];}for(int i=head[u];i;i=node[i].nxt){int v=node[i].to;if(v==father) continue;dfs(v,u);}
}
int Lca(int x, int y){if(depth[x]<depth[y]) swap(x,y);while(depth[x]!=depth[y]) x=jump[x][lg[depth[x]-depth[y]]];if(x==y) return x;for(int i=19; i>=0; --i){if(jump[x][i]!=jump[y][i]){x=jump[x][i]; y=jump[y][i];}}return jump[x][0];
}
int ans[MN];
struct Segmentree{#define lc k<<1#define rc k<<1|1struct Node{int l, r, maxn;}tr[MN<<2];void pushup(int k){tr[k].maxn=max(tr[lc].maxn,tr[rc].maxn);}void build(int k, int l, int r){tr[k].l=l, tr[k].r=r;if(l==r){tr[k].maxn=ans[l]; return;}int mid=(tr[k].l+tr[k].r)>>1;build(lc,l,mid); build(rc,mid+1,r);pushup(k); return;}int query(int k, int l, int r){if(tr[k].l>=l&&tr[k].r<=r) return tr[k].maxn;int mid=(tr[k].l+tr[k].r)>>1, res=0;if(l<=mid) res=max(res,query(lc,l,r));if(r>mid) res=max(res,query(rc,l,r));return res;}
}tr;
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);lg[0]=-1; for(int i=1; i<MN; ++i) lg[i]=lg[i>>1]+1;cin>>T; while(T--){cin>>n>>m>>q;for(int i=1; i<=m; ++i){int u, v; cin>>u>>v;side[i]={u,v,i};}cnttt=n; tottt=0;for(int i=1; i<=n+n; ++i){father[i]=i; head[i]=0;depth[i]=0; val[i]=0;}for(int i=1; i<=m; ++i){int u=side[i].u, v=side[i].v;u=find(u), v=find(v);if(u==v) continue;++cnttt; val[cnttt]=side[i].w;insert(cnttt,v); insert(v,cnttt);insert(cnttt,u); insert(u,cnttt);father[u]=cnttt; father[v]=cnttt;}dfs(cnttt,0);for(int i=1; i<n; ++i){int lca=Lca(i,i+1);ans[i]=val[lca];}tr.build(1,1,n-1);while(q--){int l, r; cin>>l>>r;if(l==r) cout<<0<<" ";else cout<<tr.query(1,l,r-1)<<' ';}cout<<'\n';}return 0;
}