Tle on the last test.(#51)

怎么就我一个tle on #51，我看最慢解最后一个点也才 1.73s 啊

code：

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(register int i=l;i<=r;++i)
#define _For(i,l,r) for(register int i=r;i>=l;--i)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=6e5+10,M=sqrt(N>>1ll)+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
int n,m,u,v,l,r,t,cnt;
int A[N>>1],L[M],R[M],S[M],B[N],a[N>>1],h[N],p1[N>>1],p2[N>>1],st[N>>1],ed[N>>1],ans[N>>1];
vector<int> E[N>>1];
struct Ques{
    int l,r,L,R,t,id;
    inline bool operator<(register const Ques&rhs)const{
        if(B[l]^B[rhs.l])
          return B[l]<B[rhs.l];
        return r>rhs.r;
    }
}Q[N>>1];
inline void add(register int u,register int v){
    E[u].push_back(v);
    E[v].push_back(u);
}
namespace LCA{
	int p[N>>1],t[N>>1],z[N>>1],d[N>>1],fa[N>>1];
	inline void dfs1(register int u,register int f){
        st[u]=++cnt;
        h[cnt]=u;
		p[u]=1;
		for(int v:E[u]){
			if(v==f)
			  continue;
			d[v]=d[u]+1;
			fa[v]=u;
			dfs1(v,u);
			p[u]+=p[v];
			if(p[v]>p[z[u]])
			  z[u]=v;
		}
        ed[u]=++cnt;
        h[cnt]=u;
	}
	inline void dfs2(register int u,register int k){
		t[u]=k;
		if(!z[u])
		  return ;
		dfs2(z[u],k);
		for(int v:E[u]){
			if(v==fa[u]||v==z[u])
			  continue;
			dfs2(v,v);
		}
	}
	inline int Lca(register int u,register int v){
		while(t[u]^t[v]){
			if(d[t[u]]<d[t[v]])
              u^=v^=u^=v;
			u=fa[t[u]];
		}
		return d[u]<d[v]?u:v;
	}
	inline void init(){
		dfs1(1,1);
		dfs2(1,1);
	}
};
inline int query(register int l,register int r){
    register int x=A[l],y=A[r];
    if(x==y){
        For(i,l,r)
          if(p2[i]&1ll)
            return i;
    }
    else{
        For(i,l,R[x])
          if(p2[i]&1ll)
            return i;
        For(i,L[y],r)
          if(p2[i]&1ll)
            return i;
        For(i,x+1,y-1){
            if(!S[i])
              continue;
            For(j,L[i],R[i])
              if(p2[j]&1ll)
                return j;
        }
    }
    return -1;
}
inline void insert(register int x){
    x=h[x];
    if(p1[x]==1){
        if(p2[a[x]]&1ll)
          S[A[a[x]]]--;
        p2[a[x]]++;
    }
    else if(!p1[x]){
        p2[a[x]]++;
        if(p2[a[x]]&1ll)
          S[A[a[x]]]++;        
    }
    p1[x]++;
}
inline void del(register int x){
    x=h[x];
    if(p1[x]==1){
        if(p2[a[x]]&1ll)
          S[A[a[x]]]--;
        p2[a[x]]--;        
    }
    else if(p1[x]==2){
        p2[a[x]]--;
        if(p2[a[x]]&1ll)
          S[A[a[x]]]++;   
    }
    p1[x]--;
}
bool End;
int main(){
    n=read(),m=read();
    For(i,1,n)
      a[i]=read();
    For(i,1,n-1){
        u=read(),v=read();
        add(u,v);
    }
    LCA::init();
    For(i,1,m){
        u=read(),v=read(),l=read(),r=read();
        if(st[u]>st[v])
          u^=v^=u^=v;
        t=LCA::Lca(u,v);
        if(t==u)
          Q[i]={st[u],st[v],l,r,0,i};
        else
          Q[i]={ed[u],st[v],l,r,t,i};
    }
    t=2000;
    For(i,1,2*n)
      B[i]=(i-1)/t+1;
    For(i,1,n)
      A[i]=(i-1)/t+1;
    For(i,1,(n+t-1)/t){
        L[i]=(i-1)*t+1;
        R[i]=min(n,i*t);
    }
    stable_sort(Q+1,Q+m+1);
    l=1,r=0;
    For(i,1,m){
        while(l<Q[i].l)
          del(l++);
        while(l>Q[i].l)
          insert(--l);
        while(r<Q[i].r)
          insert(++r);
        while(r>Q[i].r)
          del(r--);
        if(Q[i].t)
          insert(st[Q[i].t]);
        ans[Q[i].id]=query(Q[i].L,Q[i].R);
        if(Q[i].t)
          del(st[Q[i].t]);
    }
    For(i,1,m){
        write(ans[i]);
        putchar('\n');
    }
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}