\(\text{Problem}:\)题目链接
\(\text{Solution}:\)
\(x\) 出现奇数次，可以想到异或。
查询一条路径上某个值域的答案，可以想到主席树。
设值域确定时，一段路径的答案是 \(f(u,v)\)，则有：
\(f(u,v)=f(1,u)\oplus f(1,v)\oplus f(1,LCA(u,v))\oplus f(1,fa_{LCA(u,v)})\)
那么只需要在主席树上维护 \(1\) 到 \(x\) 的异或值即可。
注意到 \(1\leq a_{i}\leq n\)，也就是说，如 \(1\oplus 2 \oplus3=0\) 的一段区间会被误判。
我们对每个 \(a_{i}\) 随机钦定一个较大数 \(W_{a_{i}}\)，可以证明，当 \(W_{a_{i}}\in [0,2^{64})\) 时，冲突概率可以忽略不计。
然后大力查询即可。注意如果当前区间已被包含，说明一定有解。此时直接进入该区间找到答案，找到答案后就结束递归。
总时间复杂度为 \(O((n+q)\log n)\)。
\(\text{Code}:\)
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
using namespace std; const int N=600010;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,Q,a[N],W[N],f[N],d[N],siz[N],son[N],top[N];
int head[N],maxE; struct Edge { int nxt,to; }e[N<<1];
inline void Add(int u,int v) { e[++maxE].nxt=head[u]; head[u]=maxE; e[maxE].to=v; }
void DFS1(int x,int fa)
{
f[x]=fa, d[x]=d[fa]+1, siz[x]=1;
for(ri int i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa) continue;
DFS1(v,x);
siz[x]+=siz[v];
if(siz[v]>siz[son[x]]) son[x]=v;
}
}
void DFS2(int x,int topf)
{
top[x]=topf;
if(!son[x]) return;
DFS2(son[x],topf);
for(ri int i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==f[x]||v==son[x]) continue;
DFS2(v,v);
}
}
inline int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
return x;
}
int root[N];
struct Tree
{
int lc,rc,sum;
}D[N*30]; int cnt;
void Build(int &x,int l,int r)
{
x=++cnt;
if(l==r) return;
int mid=(l+r)/2;
Build(D[x].lc,l,mid);
Build(D[x].rc,mid+1,r);
}
void UpDate(int pre,int &x,int l,int r,int pos)
{
x=++cnt;
D[x]=D[pre], D[x].sum^=W[pos];
if(l==r) return;
int mid=(l+r)/2;
if(pos<=mid) UpDate(D[pre].lc,D[x].lc,l,mid,pos);
else UpDate(D[pre].rc,D[x].rc,mid+1,r,pos);
}
int G(int g1,int g2,int g3,int g4,int l,int r)
{
if(l==r) return l;
int mid=(l+r)/2;
if(D[D[g1].lc].sum^D[D[g2].lc].sum^D[D[g3].lc].sum^D[D[g4].lc].sum) return G(D[g1].lc,D[g2].lc,D[g3].lc,D[g4].lc,l,mid);
return G(D[g1].rc,D[g2].rc,D[g3].rc,D[g4].rc,mid+1,r);
}
int Ask(int g1,int g2,int g3,int g4,int l,int r,int ql,int qr)
{
if((D[g1].sum^D[g2].sum^D[g3].sum^D[g4].sum)==0) return -1;
if(l>=ql&&r<=qr) return G(g1,g2,g3,g4,l,r);
int mid=(l+r)/2;
int t=-1;
if(ql<=mid) t=max(t,Ask(D[g1].lc,D[g2].lc,D[g3].lc,D[g4].lc,l,mid,ql,qr));
if(~t) return t;
if(qr>mid) t=max(t,Ask(D[g1].rc,D[g2].rc,D[g3].rc,D[g4].rc,mid+1,r,ql,qr));
return t;
}
void DFS3(int x,int fa)
{
UpDate(root[fa],root[x],1,n,a[x]);
for(ri int i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa) continue;
DFS3(v,x);
}
}
signed main()
{
srand(time(NULL));
n=read(), Q=read();
for(ri int i=1;i<=n;i++) a[i]=read();
for(ri int i=1;i<=n;i++) W[i]=(1ll*rand()*rand()*rand()+rand())|(2ll*rand()*rand());
for(ri int i=1;i<n;i++)
{
int u,v;
u=read(), v=read();
Add(u,v), Add(v,u);
}
DFS1(1,0), DFS2(1,1);
Build(root[0],1,n);
DFS3(1,0);
for(ri int i=1;i<=Q;i++)
{
int u,v,l,r;
u=read(), v=read(), l=read(), r=read();
int lca=LCA(u,v);
printf("%lld\n",Ask(root[u],root[v],root[lca],root[f[lca]],1,n,l,r));
}
return 0;
}