为什么线段树会MLE，同时RE？

问题是在难想，请求大佬帮助！

爆炸情况

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n,T;
vector<int>Te[MAXN<<2],Tq[MAXN<<2];
int lch[MAXN<<2],rch[MAXN<<2],ans[MAXN<<2],root,nt;
int fa[MAXN],rnk[MAXN],dsucnt;
int ecnt,qcnt;
char op[50];
int read(){
	int x;
	cin>>x;
	return x;
}
struct back_m{
	int fau,fav,rnk;
}backup[MAXN];
struct e_m{
	int u,v,end,beg;
}edge[MAXN];
struct q_m{
	int id,t,u,v;
}q[MAXN];
int id(int x,int y){
	return (x-1)*n+y;
}
int find(int x){
	return x^fa[x]?find(fa[x]):x;
}
void eadd(int l,int r,int d,int &p=root,int s=1,int t=T){
	if(!p)p=++nt;
	if(l<=s&&t<=r)return Te[p].emplace_back(d),void();
	int mid=(s+t)>>1;
	if(l<=mid)eadd(l,r,d,lch[p],l,mid);
	if(mid<r)eadd(l,r,d,rch[p],mid+1,r);
}
void explore(int &p,int s=1,int t=T){
	int back_dsucnt=dsucnt;
	for(int i=0;i<Te[p].size();i++){
		int fau=find(edge[Te[p][i]].u),fav=find(edge[Te[p][i]].v);
		if(fau^fav){
			if(rnk[fau]<rnk[fav])swap(fau,fav);
			backup[++dsucnt]={fau,fav,rnk[fau]};
			fa[fav]=fau;
			if(rnk[fau]==rnk[fav])rnk[fau]++;
		}
	}
	int mid=(s+t)>>1;
	if(s<t&&p){
		for(int i=0;i<Tq[p].size();i++){
			q_m v=q[Tq[p][i]];
			int tmp=v.t;
			if(tmp<=mid)Tq[lch[p]].emplace_back(v.id);
			else Tq[rch[p]].emplace_back(v.id);
		}
		Tq[p].clear();
		if(!Tq[lch[p]].empty())explore(lch[p],s,mid);
		if(!Tq[rch[p]].empty())explore(rch[p],mid+1,t);
	}else{
		for(int i=0;i<Tq[p].size();i++){
			q_m v=q[Tq[p][i]];
			int fau=find(v.u),fav=find(v.v);
				ans[v.id]=(fau==fav);
		}
		Tq[p].clear();
	}
	while(dsucnt>back_dsucnt){
		fa[backup[dsucnt].fav]=backup[dsucnt].fav;
		rnk[backup[dsucnt].fau]=backup[dsucnt].rnk;
		dsucnt--;
	}
}
map<pair<int,int>,int>edge_num; 
int main(){
	cin>>n;
	for(int i=1;i<=2*n;i++)fa[i]=i;
	for(T=1;true;T++){
		cin>>op;
		if(op[0]=='C'){
			int u=id(read(),read()),v=id(read(),read());
			if(u>v)swap(u,v);
			if(edge_num.find({u,v})==edge_num.end())edge_num[{u,v}]=++ecnt;
			int p=edge_num[{u,v}];
			edge[p].u=u,edge[p].v=v,edge[p].end=T;
		}else if(op[0]=='O'){
			int u=id(read(),read()),v=id(read(),read());
			if(u>v)swap(u,v);
			if(edge_num.find({u,v})==edge_num.end())edge_num[{u,v}]=++ecnt;
			int p=edge_num[{u,v}];
			edge[p].u=u,edge[p].v=v,edge[p].beg=T;
		}else if(op[0]=='A'){
			qcnt++;
			q[qcnt]={qcnt,T,id(read(),read()),id(read(),read())};
		}else{
			break;
		}
	}
	for(int i=1;i<=ecnt;i++){
		eadd(edge[i].beg,edge[i].end?edge[i].end:(T+1),i);
	}
	for(int i=1;i<=qcnt;i++){
		Tq[root].emplace_back(i);
	}
	explore(root);
	for(int i=1;i<=qcnt;i++){
		cout<<(ans[i]?'Y':'N')<<'\n';
	}
	return 0;
}