树上莫队+根号平衡，复杂度 $O(n\sqrt{n})$（假设 $n,m$ 同阶）

TLE #7

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int MN=3e5+5;
const int MB=1005;

int n,m,B;
int bl[MN],L[MB],R[MB],sum[MB],c[MN],a[MN];

struct Node{int l,r,id,z,ql,qr;}q[MN];

int st[MN],ed[MN],E[MN<<1];
vector<int>G[MN];

namespace HLD{
	int dep[MN],fa[MN],sz[MN],hson[MN],top[MN];

	void dfs1(int u,int de){
		dep[u]=de,sz[u]=1;
		for(int v:G[u]){
			if(v==fa[u])continue;
			fa[v]=u,dfs1(v,de+1),sz[u]+=sz[v];
			if(sz[v]>sz[hson[u]])hson[u]=v;
		}
	}

	int tot=0;
	void dfs2(int u,int tp){
		top[u]=tp;st[u]=++tot;E[tot]=u;
		if(hson[u])dfs2(hson[u],tp);
		for(int v:G[u]){
			if(v==fa[u]||v==hson[u])continue;
			dfs2(v,v);
		}
		ed[u]=++tot;E[tot]=u;
	}

	int LCA(int u,int v){
		while(top[v]!=top[u]){
			if(dep[top[u]]<dep[top[v]])swap(u,v);
			u=fa[top[u]];
		}
		if(dep[u]>dep[v])swap(u,v);
		return u;
	}
};

void modify(int x){
	c[x]^=1;
	if(c[x])sum[bl[x]]++;
	else sum[bl[x]]--;
}

int get(int l,int r){
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;i++)if(c[i])return i;
		return -1;
	}
	for(int i=l;i<=R[bl[l]];i++)if(c[i])return i;
	for(int i=L[bl[r]];i<=r;i++)if(c[i])return i;
	for(int i=bl[l]+1;i<=bl[r]-1;i++){
		if(sum[i]==0)continue;
		for(int j=L[i];j<=R[i];j++)if(c[j])return j;
	}
	return -1;
}

int ans[MN],len;

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	n=read(),m=read();B=(int)(sqrt(n));memset(L,63,sizeof(L));
	for(int i=1;i<=n;i++)a[i]=read(),bl[i]=(i-1)/B+1;
	for(int i=1;i<=n;i++)L[bl[i]]=min(L[bl[i]],i),R[bl[i]]=max(R[bl[i]],i);
	for(int i=2;i<=n;i++){
		int u=read(),v=read();
		G[u].push_back(v),G[v].push_back(u);
	}

	// for(int i=1;i<=bl[n];i++)cout<<L[i]<<" ";puts("");
	// for(int i=1;i<=bl[n];i++)cout<<R[i]<<" ";puts("");

	HLD::dfs1(1,1),HLD::dfs2(1,1);
	// puts("ok");
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),l=read(),r=read();
		q[i].ql=l,q[i].qr=r,q[i].id=i;
		if(st[u]>st[v])swap(u,v);
		if(ed[u]>ed[v])q[i].l=st[u],q[i].r=st[v];
		else{
			int z=HLD::LCA(u,v);
			q[i].z=z,q[i].l=ed[u],q[i].r=st[v];
		}
	}
	// puts("ok");

	len=(int)(n*2/(int)(sqrt(m)));
	sort(q+1,q+m+1,[](const Node &x,const Node &y){
		int bx=(x.l-1)/len+1,by=(y.l-1)/len+1;
		if(bx!=by)return bx<by;
		return (bx&1)?(x.r<y.r):(x.r>y.r);
	});

	// puts("ok");
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		int ql=q[i].l,qr=q[i].r;
		// cout<<ql<<" "<<qr<<endl;
		while(l>ql)modify(a[E[--l]]);
		while(r<qr)modify(a[E[++r]]);
		while(l<ql)modify(a[E[l++]]);
		while(r>qr)modify(a[E[r--]]);
		if(q[i].z)modify(a[q[i].z]);
		ans[q[i].id]=get(q[i].ql,q[i].qr);
		if(q[i].z)modify(a[q[i].z]);
	}

	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';

	return 0;
}