题目分析:
很无聊的一道题目。首先区间内单点对应异或值的询问容易想到trie树。由于题目在树上进行,case1将路径分成两段,然后dfs的时候顺便可持久化trie树做询问。case2维护dfs序,对dfs序建可持久化的trie树。这样做的空间复杂度是O(nw),时间复杂度是O(nw).
代码:
#include<bits/stdc++.h>
using namespace std; const int maxn=; int n,q;
int v[maxn];
vector<int> g[maxn]; vector<pair<int,int> > qy[maxn];
vector<pair<int,int> > vec; int ans[maxn],num,kd[maxn];
int dep[maxn],dfsin[maxn],dfsout[maxn],fa[maxn]; vector<pair<int,int> > Lca[maxn];
int pre[maxn]; int found(int x){
int rx = x; while(pre[rx] != rx) rx = pre[rx];
while(pre[x] != rx){
int t = pre[x]; pre[x] = rx; x = t;
}
return rx;
} void dfs(int now,int dp,int f){
dfsin[now] = dfsout[now] = ++num;fa[now] = f; dep[now] = dp;
for(auto pr:Lca[now]){
if(dep[pr.first] == ) continue;
int la = found(pr.first);
qy[now].push_back(make_pair(la,pr.second));
qy[pr.first].push_back(make_pair(la,pr.second));
}
for(auto i:g[now]){
if(i == f) continue;
dfs(i,dp+,now);
dfsout[now] = dfsout[i];
}
pre[found(now)] = found(f);
} void read(){
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++) scanf("%d",&v[i]);
for(int i=;i<n;i++){
int x,y; scanf("%d%d",&x,&y);
g[x].push_back(y); g[y].push_back(x);
}
for(int i=;i<=q;i++){
int cas; scanf("%d",&cas);
if(cas == ){
int x,y; scanf("%d%d",&x,&y);
vec.push_back(make_pair(x,i));kd[i] = y;
}else{
int x,y,z; scanf("%d%d%d",&x,&y,&z);
Lca[x].push_back(make_pair(y,i));
if(x!=y) Lca[y].push_back(make_pair(x,i));
kd[i] = z;
}
}
for(int i=;i<=n;i++) pre[i] = i;
dfs(,,);
} int his[maxn],om;
int sz[maxn*],ch[maxn*][]; void follow(int pt,int last,int dt){
int hbit = ;
while(hbit!=-){
if((<<hbit)&dt){
ch[pt][] = ch[last][];
ch[pt][] = ++num;
pt = num; last = ch[last][];
sz[pt] = sz[last]+;
}else{
ch[pt][] = ch[last][];
ch[pt][] = ++num;
pt = num; last = ch[last][];
sz[pt] = sz[last]+;
}
hbit--;
}
} void ins(int now){
int last = his[om-];
num++;int pt = num; sz[pt] = sz[last]+;
his[om] = num;
follow(pt,last,v[now]);
} int query(int now,int last,int z){
now = his[now]; last = his[last];
int hbit = ;
while(hbit!=-){
if((<<hbit)&z){
if(sz[ch[now][]]-sz[ch[last][]]){
now = ch[now][];last = ch[last][];
}else{
z -= (<<hbit);now = ch[now][];last = ch[last][];
}
}else{
if(sz[ch[now][]]-sz[ch[last][]]){
z += (<<hbit);
now = ch[now][];last = ch[last][];
}else{
now = ch[now][];last = ch[last][];
}
}
hbit--;
}
return z;
} void del(int now){his[om] = ;} void dfs2(int now){
om++;ins(now);
for(auto pr:qy[now]){
int last = dep[pr.first]-,data = kd[pr.second];
ans[pr.second] = max(ans[pr.second],query(dep[now],last,data));
}
for(auto i:g[now]){
if(i == fa[now]) continue;
dfs2(i);
}
del(now);om--;
} void dfs3(int now){
om++;ins(now);
for(auto i:g[now]){
if(i == fa[now]) continue;
dfs3(i);
}
} void work(){
num = ;his[] = ;
dfs2();
memset(ch,,sizeof(ch));memset(sz,,sizeof(sz));
num = ;his[] = ;om = ;
dfs3();
for(auto pr:vec){
int st = dfsin[pr.first],ed = dfsout[pr.first];
ans[pr.second] = query(ed,st-,kd[pr.second]);
}
for(int i=;i<=q;i++) printf("%d\n",ans[i]);
} int main(){
read();
work();
return ;
}