题目描述
现在有一颗以1为根节点的由n个节点组成的树，树上每个节点上都有一个权值vi。
现在有Q 次操作，操作如下:
1 x y 查询节点x的子树中与y异或结果的最大值
2 x y z 查询路径x到y上点与z异或结果最大值
输入
第一行是两个数字n, Q;
第二行是n个数字用空格隔开，第i个数字vi表示点i上的权值
接下来n-1行，每行两个数，x,y，表示节点x与y之间有边
接下来Q行，每一行为一个查询，格式如上所述.
1 < n, Q ≤ 100000 ，查询1中的y ≤ 2^30 ，查询2中的z ≤ 2^30
输出
对于每一个查询，输出一行，表示满足条件的最大值。
样例输入
7 5
1 3 5 7 9 2 4
1 2
1 3
2 4
2 5
3 6
3 7
1 3 5
2 4 6 3
1 5 5
2 5 7 2
1 1 9
1 3 5 7 9 2 4
1 2
1 3
2 4
2 5
3 6
3 7
1 3 5
2 4 6 3
1 5 5
2 5 7 2
1 1 9
样例输出
7
6
12
11
14
6
12
11
14
刚看到这道题有点不知所措，这异或最大值怎么求？但仔细想想就能发现取异或最大值是一种贪心的思想。首先，异或的运算原理是每一位相同为0，不同为1，那么我们肯定希望能得到1而不是0。而每一位取1对答案的贡献显然是不一样的，位数高的位取1显然要使答案更大一些。对于给出的一个数z，要使一个数和他的异或结果最大，当然是从高位开始，只要这一位能与z对应的这一位不一样那么就能使答案变大。而每一位只有0或1两种取值，恰好可以和线段树的左右子树对应。那么要使一个序列中的数与z的异或结果最大，可以建一棵32层的线段树(第一层只是代表一个根节点)，从上往下的每一层就代表从高到低的每一位的取值，左子树代表0，右子树代表1，把序列的每一个数按二进制判断在每层应该往左走还是往右走，然后线段树的每个节点维护区间数的个数。这样查找时只要看与z对应位不同的那边子树中是否有数，有就往那边走，这样可以最大化每一层对答案的贡献。那么怎么把树上的一棵子树或者一条路径变成一个序列？dfs序！出栈入栈序！dfs序维护每个点的子树对应的区间，出栈入栈序维护从上到下的一条链的区间，两点间路径可以看成是这两点lca分别到这两点的链。因为要求区间中与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));
}
}
}