P4592 [TJOI2018] 异或
考虑一个弱化版：
多次查询，每次查询一个区间 \([l,r]\) 中的元素异或 \(x\) 的最大值。
异或最大值容易想到 01-trie 树，回顾 01-trie 树处理静态集合的做法：
先将每个元素的二进制表示插入 trie。
对于询问的数 \(x\)，从高位往低位考虑。
设 \(x\) 的当前位为 \(k\in \set{0,1}\)，如果存在 \(1-k\) 的儿子则往它走，否则往 \(k\) 走。
对于区间查询可以记录每一个结点经过的元素个数的前缀和，对于查询区间的元素中是否存在儿子用前缀和相减即可。
每一个点都开一棵 trie 树显然不行，但一次只增加一个元素，可以使用可持久化 trie 树。
回到这题，子树查询显然可以用 dfs 序变成区间查询，还剩下链查询。
事实上，观察上面的做法可以发现其并没有特殊性。也就是说能用前缀和就可以使用它。
考虑一种树上前缀和，设 \(a_i\) 为点 \(i\) 到根路径上的点权的前缀和。
则有链 \((u,v)\) 上点权的和为 \(a_u+a_v-a_{\operatorname{LCA}(u,v)}-a_{fa_{\operatorname{LCA}(u,v)}}\)。
使用相同的方法套到 trie 树上就行，时间复杂度 \(\mathcal O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
const int V=30,N=100005;
vector<int>s[N];int idx,tot;
int a[N],fa[N],dep[N],rt1[N],rt2[N];
int n,q,dfn[N],siz[N],top[N],hson[N];
struct node{int ch[2],c;}tr[N*(V+5)<<1];
void ins(int v,int &x,int y){tr[x=++idx]=tr[y],tr[x].c++;for(int i=V,p=x;~i;i--){bool t=v>>i&1;tr[p].ch[t]=++idx,y=tr[y].ch[t];tr[p=tr[p].ch[t]]=tr[y],tr[p].c++;}
}
int query(int v,int x,int y,int z,int w){int res=0;for(int i=V;~i;i--){int cx=tr[x].ch[~v>>i&1];int cy=tr[y].ch[~v>>i&1];int cz=tr[z].ch[~v>>i&1];int cw=tr[w].ch[~v>>i&1];if(tr[cx].c+tr[cy].c-tr[cz].c-tr[cw].c)x=cx,y=cy,z=cz,w=cw,res|=1<<i;elsex=tr[x].ch[v>>i&1],y=tr[y].ch[v>>i&1],z=tr[z].ch[v>>i&1],w=tr[w].ch[v>>i&1];}return res;
}
void dfs1(int x){ins(a[x],rt2[x],rt2[fa[x]]);ins(a[x],rt1[tot+1],rt1[tot]);dfn[x]=++tot,dep[x]=dep[fa[x]]+1;for(auto p:s[x]) if(p^fa[x]){fa[p]=x,dfs1(p),siz[x]+=siz[p];if(siz[p]>siz[hson[x]]) hson[x]=p;}siz[x]++;
}
void dfs2(int x,int t){top[x]=t;if(!hson[x]) return;dfs2(hson[x],t);for(auto p:s[x])if(p^fa[x]&&p^hson[x]) dfs2(p,p);
}
int LCA(int x,int y){for(;top[x]^top[y];x=fa[top[x]])if(dep[top[x]]<dep[top[y]]) swap(x,y);return dep[x]<dep[y]?x:y;
}
int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),s[u].emplace_back(v),s[v].emplace_back(u);for(dfs1(1),dfs2(1,1);q--;){int op,x,y,z;scanf("%d%d%d",&op,&x,&y);if(op&1) printf("%d\n",query(y,rt1[dfn[x]+siz[x]-1],0,rt1[dfn[x]-1],0));else{scanf("%d",&z);int f=LCA(x,y);printf("%d\n",query(z,rt2[x],rt2[y],rt2[f],rt2[fa[f]]));}}return 0;
}