UOJ #715. 【北大集训2021】小明的树

题面传送门
大诈骗题。
发现对着题目中那个东西不太好想，所以考虑没有被点亮的点，发现如果满足题目中那个条件，那么没有被点亮的点构成一个包含1的联通块。
众所周知联通块个数等于点数减边数，然后就可以用这个东西开个线段树随便维护一下最小值就好了。
也不用LCT，只要两个点在a序列中的排名就好了。
时间复杂度\(O((n+Q)\log n)\)，凭借快读优势跑到rk1
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N (500000+5)
#define M ((1<<19)+5)
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    templateinline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    templateinline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
int n,m,k,P[N],x,y,X[N],Y[N];
namespace Tree{
	#define ls now<<1
	#define rs now<<1|1
	int F1[N<<2],G1[N<<2],Si[N<<2];ll F2[N<<2],G2[N<<2];I void P1(int now,int w){G1[now]+=w;F1[now]+=w;}I void P2(int now,int w){F2[now]+=w*Si[now];G2[now]+=w;}
	I void Up(int now){F1[ls]^F1[rs]?(F1[ls]>1;BD(l,m,ls);BD(m+1,r,rs);Up(now);}
	I void I1(int x,int y,int w,int l=1,int r=n-1,int now=1){if(x<=l&&r<=y) return P1(now,w);int m=l+r>>1;x<=m&&(I1(x,y,w,l,m,ls),0);y>m&&(I1(x,y,w,m+1,r,rs),0);Up(now);}
	I void I2(int x,int y,int w,int l=1,int r=n-1,int now=1){if(x<=l&&r<=y) return P2(now,w);int m=l+r>>1;x<=m&&(I2(x,y,w,l,m,ls),0);y>m&&(I2(x,y,w,m+1,r,rs),0);Up(now);}
	#undef ls
	#undef rs
}
I void Ins(int x,int y,int w){min(P[x],P[y])^1&&(Tree::I1(1,min(P[x],P[y])-1,w),0);max(P[x],P[y])^n&&(Tree::I2(max(P[x],P[y]),n-1,w),0);}
int main(){
	freopen("1.in","r",stdin);
	RI i;fin>>n>>m;for(i=1;i>X[i]>>Y[i];for(i=1;i>x,P[x]=i;P[1]=n;Tree::BD();
	for(i=1;i>x>>y,Ins(x,y,1),fin>>x>>y,Ins(x,y,-1),fout<