现在有一颗以1为根节点的由n个节点组成的树，树上每个节点上都有一个权值vi。
现在有Q 次操作，操作如下:
1 x y 查询节点x的子树中与y异或结果的最大值
2 x y z 查询路径x到y上点与z异或结果最大值
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int cnt;
int num;
int tot;
int n,m;
int opt;
int res1;
int res2;
int x,y,z;
int v[100010];
int d[100010];
int s[100010];
int t[100010];
int to[200010];
int in[100010];
int out[100010];
int ioth[200010];
int head[100010];
int dfsth[100010];
int f[100010][17];
int next[200010];
int root1[200010];
int root2[200010];
int ls1[10000010];
int rs1[10000010];
int ls2[10000010];
int rs2[10000010];
int sum1[10000010];
int sum2[10000010];
void add(int x,int y)
{
tot++;
next[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void dfs(int x,int fa)
{
d[x]=d[fa]+1;
f[x][0]=fa;
in[x]=++cnt;
s[x]=++num;
ioth[cnt]=x;
dfsth[num]=x;
for(int i=1;i<=16;i++)
{
f[x][i]=f[f[x][i-1]][i-1];
}
for(int i=head[x];i;i=next[i])
{
if(to[i]!=fa)
{
dfs(to[i],x);
}
}
out[x]=++cnt;
t[x]=num;
ioth[cnt]=-x;
}
int lca(int x,int y)
{
if(d[x]<d[y])
{
swap(x,y);
}
int dep=d[x]-d[y];
for(int i=0;i<=16;i++)
{
if(((1<<i)&dep)!=0)
{
x=f[x][i];
}
}
if(x==y)
{
return x;
}
for(int i=16;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int updata1(int pre,int k,int v)
{
int rt=++res1;
ls1[rt]=ls1[pre];
rs1[rt]=rs1[pre];
sum1[rt]=sum1[pre]+1;
if(k<0)
{
return rt;
}
if(((1<<k)&v)==0)
{
ls1[rt]=updata1(ls1[pre],k-1,v);
}
else
{
rs1[rt]=updata1(rs1[pre],k-1,v);
}
return rt;
}
int query1(int l,int r,int v,int k)
{
if(k<0)
{
return 0;
}
if(((1<<k)&v)==0)
{
if(sum1[rs1[r]]-sum1[rs1[l]]>0)
{
return query1(rs1[l],rs1[r],v,k-1)+(1<<k);
}
else
{
return query1(ls1[l],ls1[r],v,k-1);
}
}
else
{
if(sum1[ls1[r]]-sum1[ls1[l]]>0)
{
return query1(ls1[l],ls1[r],v,k-1)+(1<<k);
}
else
{
return query1(rs1[l],rs1[r],v,k-1);
}
}
}
int updata2(int pre,int k,int v,int x)
{
int rt=++res2;
ls2[rt]=ls2[pre];
rs2[rt]=rs2[pre];
sum2[rt]=sum2[pre]+x;
if(k<0)
{
return rt;
}
if(((1<<k)&v)==0)
{
ls2[rt]=updata2(ls2[pre],k-1,v,x);
}
else
{
rs2[rt]=updata2(rs2[pre],k-1,v,x);
}
return rt;
}
int query2(int x,int y,int fa,int anc,int v,int k)
{
if(k<0)
{
return 0;
}
if(((1<<k)&v)==0)
{
if(sum2[rs2[x]]+sum2[rs2[y]]-sum2[rs2[fa]]-sum2[rs2[anc]]>0)
{
return query2(rs2[x],rs2[y],rs2[fa],rs2[anc],v,k-1)+(1<<k);
}
else
{
return query2(ls2[x],ls2[y],ls2[fa],ls2[anc],v,k-1);
}
}
else
{
if(sum2[ls2[x]]+sum2[ls2[y]]-sum2[ls2[fa]]-sum2[ls2[anc]]>0)
{
return query2(ls2[x],ls2[y],ls2[fa],ls2[anc],v,k-1)+(1<<k);
}
else
{
return query2(rs2[x],rs2[y],rs2[fa],rs2[anc],v,k-1);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,0);
for(int i=1;i<=num;i++)
{
root1[i]=updata1(root1[i-1],30,v[dfsth[i]]);
}
for(int i=1;i<=cnt;i++)
{
root2[i]=updata2(root2[i-1],30,v[abs(ioth[i])],ioth[i]>0?1:-1);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&opt);
if(opt==1)
{
scanf("%d%d",&x,&y);
printf("%d\n",query1(root1[s[x]-1],root1[t[x]],y,30));
}
else
{
scanf("%d%d%d",&x,&y,&z);
int anc=lca(x,y);
printf("%d\n",query2(root2[in[x]],root2[in[y]],root2[in[anc]],root2[in[f[anc][0]]],z,30));
}
}
}
BZOJ5338[TJOI2018]xor——主席树+出栈入栈序+dfs序+LCA
原文：https://www.cnblogs.com/Khada-Jhin/p/9435985.html