这道题有这样一个解法：
首先把边依次加到图中，若当前这条边与图中的边形成了环，那么把这个环中最早加进来的边弹出去
并将每条边把哪条边弹了出去记录下来：ntr[i] = j，特别地，要是没有弹出边，ntr[i] = 0;
这个显然是可以用LCT来弄的对吧。
然后对于每个询问，我们的答案就是对l~r中ntr小于l的边求和，并用n减去这个值
正确性可以想一下：
如果一条边的ntr >= l,那么显然他可以与从l ~ r中的边形成环，那么它对答案没有贡献
反之如果一条边的ntr < l那么它与从l ~ r中的边是不能形成环的，那么他对答案的贡献为-1
#include<cstdio> #include<cctype> #include<cstring> #define lc ch[x][0] #define rc ch[x][1] #include<algorithm> using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=200010; const int maxnode=2000010; const int INF=1000000000; int fa[maxn],pre[maxn],mn[maxn],val[maxn],flip[maxn],ch[maxn][2]; void maintain(int x) { mn[x]=x; if(val[mn[lc]]<val[mn[x]]) mn[x]=mn[lc]; if(val[mn[rc]]<val[mn[x]]) mn[x]=mn[rc]; } void pushdown(int x) { if(!flip[x]) return; flip[lc]^=1;flip[rc]^=1; swap(lc,rc);flip[x]=0; } void rotate(int x,int d) { pushdown(x);int y=pre[x],z=pre[y]; ch[y][d^1]=ch[x][d];pre[ch[x][d]]=y; ch[z][ch[z][1]==y]=x;pre[x]=z; ch[x][d]=y;pre[y]=x;maintain(y); } void splay(int x) { int rt=x;while(pre[rt]) rt=pre[rt]; if(rt!=x) { fa[x]=fa[rt];fa[rt]=0; while(pre[x]) pushdown(pre[x]),rotate(x,ch[pre[x]][0]==x); maintain(x); } else pushdown(x); } void access(int x) { for(int y=0;x;x=fa[x]) { splay(x);pre[ch[x][1]]=0;fa[ch[x][1]]=x; ch[x][1]=y;pre[y]=x;fa[y]=0; maintain(x);y=x; } } void makeroot(int x) {access(x);splay(x);flip[x]^=1;} void link(int x,int y){makeroot(x);fa[x]=y;} void cut(int x,int y) { makeroot(x);access(y);splay(y); pre[ch[y][0]]=0;ch[y][0]=0;maintain(y); } int find(int x) { access(x);splay(x); while(ch[x][0]) x=ch[x][0]; return x; } int query(int x,int y) { makeroot(x);access(y);splay(y); return mn[y]; } int u[maxn],v[maxn],f[maxn],root[maxn],ToT; int ls[maxnode],rs[maxnode],s[maxnode]; void build(int& y,int x,int l,int r,int pos) { s[y=++ToT]=s[x]+1;if(l==r) return; ls[y]=ls[x];rs[y]=rs[x];int mid=l+r>>1; if(pos<=mid) build(ls[y],ls[x],l,mid,pos); else build(rs[y],rs[x],mid+1,r,pos); } int query(int y,int l,int r,int pos) { if(l==r) return s[y]; int mid=l+r>>1; if(pos<=mid) return query(ls[y],l,mid,pos); return query(rs[y],mid+1,r,pos)+s[ls[y]]; } int main() { int n=read(),m=read(),q=read(); for(int i=0;i<=n;i++) val[i]=INF; for(int i=1;i<=m;i++) { u[i]=read();v[i]=read();val[i+n]=i; if(u[i]==v[i]) {f[i]=i;continue;} if(find(u[i])!=find(v[i])) link(u[i],i+n),link(i+n,v[i]); else { int k=query(u[i],v[i]);f[i]=k-n; cut(u[k-n],k);cut(k,v[k-n]); link(u[i],i+n);link(i+n,v[i]); } } for(int i=1;i<=m;i++) build(root[i],root[i-1],0,m,f[i]); while(q--) { int l=read(),r=read(); printf("%d ",n-query(root[r],0,m,l-1)+query(root[l-1],0,m,l-1)); } return 0; }