CF840E In a Trap
题意
有一颗以1为根的树，每个点上有一个点权ai，每次询问路径u到v上最大的 $ai \bigoplus dist(i,v) $，保证u为v的祖先
题解
有意思的题，之前考过一道类似的，那题场切了，这题不会。
首先我们将值域折半，将 \(dis\) 产生的影响分成前 \(8\) 位和后 \(8\) 位。
对于每个点，向上每 \(256\) 块一个点，也就是说对于每一块内 \(dis\) 的值前 \(8\) 位不变，后 \(8\) 位会变。
考虑整块的答案如何快速求，首先我们对于第 \(i\) 块中某个位置 \(x\) 的贡献是这样的 $f(x,v) = dis(x,k)\oplus a_x\oplus(256i) $ 其中 \(k\) 是块头。
我们对于每一个 \(i\) 作为块头进行处理，我们将块中元素 \(a_j=>a_j\oplus t\)，\(t\) 是 \(a_j\) 在块中的位置。
我们考虑这个块作为第 \(k\) 个块时的贡献，我们将修改后的数全部插入一个 01trie，这样就相当于在 01trie中查 \(256k\) 能异或出的最大值。
但是这样空间有点炸，可以卡一下空间，只插入前 \(8\) 位，找到前 \(8\) 位后最大值后找到这个前 \(8\) 位最大的后 \(8\) 位拼上。
但是还不行，直接用 \(f_{i,x}\) 表示 \(x\) 作为块头的块是第 \(i\) 个块的最大值，在预处理 \(f\) 数组时重复用 01trie 就好了。
最后整块暴力跳，散块暴力即可，时间复杂度 \(O(n\sqrt{n}logn+q\sqrt{n}logn)\)。
点击查看代码
#include <bits/stdc++.h>
#define pii pair<int,int>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int f(0) ; rg char c(gc()) ;
while(!isdigit(c)) f |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (f?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
bool S_GND ;
const int N = 5e4+5 ;
const int B = 256 ;
int n,Q,top ;
int pos[N],st[N] ;
int a[N],fa[N],f[B][N],dep[N],ans[N*10],mx[B] ;
vector<int>e[N] ;
vector<pii>q[N] ;
int cmp(pii x,pii y) {return dep[x.first] > dep[y.first] ;}
struct Trie
{
int tr[B*10][2],top = 1 ;
Trie(){me(tr,0) ;}
void clear() {top = 1,tr[1][0] = tr[1][1] = 0 ;}
void Insert(int x)
{
int p = 1 ;
ROF(i,8,0,1)
{
int pos = (x>>i)&1 ;
if(!tr[p][pos]) tr[p][pos] = ++top,tr[top][0] = tr[top][1] = 0 ;
p = tr[p][pos] ;
}
}
int Query(int x)
{
int res = 0,p = 1 ;
ROF(i,8,0,1)
{
int pos = (x>>i)&1 ;
if(!tr[p][0] && !tr[p][1]) break ;
if(tr[p][!pos]) p = tr[p][!pos],res |= 1<<i ;
else p = tr[p][pos] ;
}
return res ;
}
}g ;
void Dfs(int x)
{
if(dep[x] >= B)
{
int T = B,tot = 0,now = x ; g.clear(),me(mx,0) ;
while(T--) g.Insert(a[now]>>8),mx[a[now]>>8] = max(mx[a[now]>>8],(a[now]&255)^tot),++tot,now = fa[now] ;
FOR(i,0,B-1,1)
{
int res = g.Query(i) ;
f[i][x] = (res<<8)+mx[i^res] ;
}
}
for(auto v:e[x]) if(v != fa[x])
fa[v] = x,dep[v] = dep[x]+1,Dfs(v) ;
}
int Get(int x)
{
return st[pos[x]-B] ;
}
void Solve(int x)
{
int res = 0,tot = 0,now = x ;
st[++top] = x,pos[x] = top,sort(q[x].begin(),q[x].end(),cmp) ;
for(auto [v,id]:q[x])
{
while(dep[now] > B && dep[Get(now)] > dep[v]) res = max(res,f[tot][now]),++tot,now = Get(now) ; //assert(tot < B)
int gkd = now,p = 0 ; while(gkd != v) ans[id] = max(ans[id],(p+tot*B)^a[gkd]),++p,gkd = fa[gkd] ; ans[id] = max({ans[id],res,(p+tot*B)^a[gkd]}) ;
}
for(auto v:e[x]) if(v != fa[x]) Solve(v) ; --top ;
}
signed main()
{
// cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
// freopen(".in","r",stdin) ;
// freopen(".out","w",stdout) ;
read(n,Q) ;
FOR(i,1,n,1) read(a[i]) ;
FOR(i,2,n,1)
{
int u,v ; read(u,v) ;
e[u].pb(v),e[v].pb(u) ;
}
FOR(i,1,Q,1)
{
int u,v ; read(u,v) ;
q[v].pb({u,i}) ;
}
Dfs(1),Solve(1) ;
FOR(i,1,Q,1) print(ans[i]),enter ;
return 0 ;
}