考虑树的性质：n个点，n-1条边，连通图

前两个用老套路，考虑枚举右端点，线段树维护左端点情况

n不同，但是，一个图是树，那么必然n-(n-1)=1，如果最小值就是1，那么是可以维护的。

所以如果保证这些左端点到r的点构成n-1条边的连通图，就可以直接求答案了。

但是并不一定只有n-1条边，有n-1条边也可能不连通

考虑不一定有n-1条边，和有n-1条边但是不连通的条件是：有环！

只有[l,r]没有环，才可能之后会构成一个树

并且我们可以发现，[l,r]有环，那么l'<=l,r'>=r的[l',r']都一定有环

所以可以尺取法！

枚举R的同时，L卡住左边界，使得[L,R]没有环。LCT维护一下

只有左端点位于[L,R]才可能是树，且点数-边数最小值是1

维护最小值和最小值出现次数即可。

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}}//using namespace Modulo;namespace Miracle{const int N=2e5+5;const int inf=0x3f3f3f3f;const int mv[4][2]={ {+1,0},{-1,0},{ 0,-1},{ 0,+1}};int a[2002][2002];int n;int ha,li;pair
           
            pos[N];struct node{ int ch[2]; int fa; int rev;}t[N];int L,R;bool nrt(int x){ return (t[t[x].fa].ch[0]==x||t[t[x].fa].ch[1]==x);}void rotate(int x){ int y=t[x].fa,d=t[y].ch[1]==x; t[t[y].ch[d]=t[x].ch[!d]].fa=y; if(nrt(y)) t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x; else t[x].fa=t[y].fa; t[t[x].ch[!d]=y].fa=x;}int sta[N];#define ls t[x].ch[0]#define rs t[x].ch[1]void rev(int x){ t[x].rev^=1; swap(t[x].ch[0],t[x].ch[1]);}void pd(int x){ if(t[x].rev){ rev(ls);rev(rs); t[x].rev=0; }}void splay(int x){ int y=x,z=0; sta[++z]=y; while(nrt(y)) y=t[y].fa,sta[++z]=y; while(z) pd(sta[z--]); while(nrt(x)){ y=t[x].fa,z=t[y].fa; if(nrt(y)){ rotate((t[y].ch[0]==x)==(t[z].ch[0]==y)?y:x); } rotate(x); }}void access(int x){ for(reg y=0;x;y=x,x=t[x].fa){ splay(x);t[x].ch[1]=y; }}void makert(int x){ access(x);splay(x);rev(x);}int findrt(int x){ access(x);splay(x); while(t[x].ch[0]) x=t[x].ch[0]; splay(x); return x;}bool link(int x,int y){ makert(x); if(findrt(y)!=x){ t[x].fa=y; return true; }else return false;}void cut(int x,int y){ makert(x);access(y);splay(y); if(t[y].ch[0]==x&&!t[x].ch[0]&&!t[x].ch[1]){ t[x].fa=0;t[y].ch[0]=0; }}void dele(int x){ int nx=pos[x].fi,ny=pos[x].se; for(reg i=0;i<4;++i){ int tx=nx+mv[i][0],ty=ny+mv[i][1]; if(a[tx][ty]){ int p=a[tx][ty]; if(p>=L&&p<=R){ cut(x,p); } } }}int got[10];bool che(int x){ bool fl=true; int nx=pos[x].fi,ny=pos[x].se; int ct=0; for(reg i=0;i<4;++i){ int tx=nx+mv[i][0],ty=ny+mv[i][1]; if(a[tx][ty]){ int p=a[tx][ty]; if(p>=L&&p<=R){ bool lp=link(x,p); if(lp==false) { fl=false;break; } got[++ct]=p; } } } if(!fl){ for(reg i=1;i<=ct;++i) cut(x,got[i]); } return fl;}#undef ls#undef rsstruct po{ int mi,cnt; po(){mi=inf,cnt=1;} po friend operator +(po a,po b){ po c;c.mi=min(a.mi,b.mi);c.cnt=0; if(a.mi==c.mi) c.cnt+=a.cnt; if(b.mi==c.mi) c.cnt+=b.cnt; return c; }};namespace seg{struct tr{ po v; int add;}t[4*N];#define ls (x<<1)#define rs (x<<1|1)#define mid ((l+r)>>1)void pushup(int x){ t[x].v=t[ls].v+t[rs].v;}void tag(int x,int c){ t[x].add+=c; t[x].v.mi+=c;}void pushdown(int x){ if(t[x].add){ tag(ls,t[x].add);tag(rs,t[x].add); t[x].add=0; }}void build(int x,int l,int r){ if(l==r){ t[x].add=0;t[x].v.mi=0;t[x].v.cnt=1;return; } build(ls,l,mid); build(rs,mid+1,r); pushup(x);}void upda(int x,int l,int r,int L,int R,int c){ if(L<=l&&r<=R){ tag(x,c);return; } pushdown(x); if(L<=mid) upda(ls,l,mid,L,R,c); if(mid
            
             =L&&p<=R){ seg::upda(1,1,n,L,p,-1); } } } po now=seg::query(1,1,n,L,R); if(now.mi==1){ ans+=now.cnt; } } ot(ans); return 0;}}signed main(){ Miracle::main(); return 0;}/* Author: *Miracle**/
            
           
          
         
        
       
      
     

本题处理树的连通性还是不错的思路：变成处理有没有环

环可以尺取法处理，使得边数<=n-1,然后点数-边数最小是1，就保证了是一棵树。