怪异题。
阈值分治。权值不超过 \(2^{16}=65536\)，于是把前后八位砍开。把每个点和上边 \(256\) 个点分成一块，那么每块内的 \(dis\) 的前八位是相同的，因此可以分开考虑。
前边 \(8\) 位设一个 \(f_{x,i}\) 表示跳了 \(i\) 块跳到 \(x\)，这一块的前八位最大值。这个暴力把这一块的所有点插进 01Trie 然后枚举一遍 \(i\) 暴力判就可以。
后边 \(8\) 位设一个 \(g_{i}\) 为前八位权值为 \(i\) 时异或 \(dis\) 的后八位最大值，这个也暴力往上扫 \(256\) 个点记录就行。然后查的时候保证前八位最大，可以通过前八位得到后八位的值。
代码很好写。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int n,m;
struct node{
int v,next;
}edge[100010];
int t,head[50010],val[50010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
struct Trie{
int cnt,trie[2100][2];
void clear(){
for(int i=0;i<=cnt;i++)trie[i][0]=trie[i][1]=0;cnt=0;
}
void ins(int x){
int p=0;
for(int i=7;i>=0;i--){
int w=(x>>i)&1;
if(!trie[p][w])trie[p][w]=++cnt;
p=trie[p][w];
}
}
int query(int x){
int p=0,ans=0;
for(int i=7;i>=0;i--){
int w=(x>>i)&1;ans<<=1;
if(trie[p][w^1])ans|=1,p=trie[p][w^1];
else p=trie[p][w];
}
return ans;
}
}T;
int fa[50010],f[50010][256],g[256],pre[50010],dep[50010];
void dfs(int x,int faa){
fa[x]=faa;dep[x]=dep[faa]+1;
if(dep[x]>=256){
T.clear();int u=x;
memset(g,0,sizeof(g));
for(int dis=0;dis<(1<<8);u=fa[u],dis++){
g[val[u]>>8]=max(g[val[u]>>8],dis^val[u]&255);
T.ins(val[u]>>8);
}
pre[x]=u;
for(int i=0;i<(1<<8);i++){
int ans=T.query(i);
f[x][i]=ans<<8|g[ans^i];
}
}
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=faa)dfs(edge[i].v,x);
}
}
int query(int x,int y){
int dis=0,ans=0;
while(dep[y]-dep[x]>=256)ans=max(ans,f[y][dis]),y=pre[y],dis++;
dis<<=8;
while(y!=fa[x])ans=max(ans,val[y]^dis),dis++,y=fa[y];
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&val[i]);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1,0);
while(m--){
int u,v;scanf("%d%d",&u,&v);
printf("%d\n",query(u,v));
}
return 0;
}