题目链接

P4592 [TJOI2018] 异或

解题思路

读完题目首先发现很像最大异或和问题但是在树上操作
一开始想到树剖但是树剖有两个 \(\log\) ~~但是树剖常数小~~
考虑dfs序列
由于不能对任意一颗子树建01trie所以想到可持久化。
子树查询转成 \(dfs\) 序上一段区间，而链上查询转成两条链。
这就需要两颗 \(01trie\)
看粉兔的代码很有收获。
注意可持久化01trie的空间大小！

code

#include<iostream>
#include<cstdio>
using namespace std ;

const int MAXN = 1e5+10 ;
const int MAXS = MAXN*65 ;

int n ,q ;
int a[MAXN] ;
int head[MAXN] ,edge_cnt ;
struct Edge{
	int to ,next ;
}edge[MAXN<<1] ;
inline void edge_add(int from , int to){
	edge[++edge_cnt].to = to ;
	edge[edge_cnt].next = head[from] ;
	head[from] = edge_cnt ;
}

int siz[MAXS] ,ch[MAXS][2] ,cnt ;
int rt1[MAXN] ,rt2[MAXN] ;
inline void insent(int &rt , int x , int j){//加点操作 
	ch[++cnt][0] = ch[rt][0] ;
	ch[cnt][1] = ch[rt][1] ;//生成新的节点 初始化为原来节点 
	siz[cnt] = siz[rt] ;//记录子树大小 
	rt = cnt ;//把当前节点的序号覆盖 
	++siz[rt] ;//子树大小加入新建节点  
	if (j >= 0) insent(ch[rt][x >> j & 1] , x , j - 1) ;
}

int dfn[MAXN] ,tim[MAXN] ,dep[MAXN] ,f[MAXN][17] ,dfc ;
inline void dfs(int node , int fa){
	dfn[node] = ++dfc ;
	f[node][0] = fa ;
	dep[node] = dep[fa] + 1 ;
	insent(rt1[dfc] = rt1[dfc - 1] , a[node] , 29);//DFS序 
	insent(rt2[node] = rt2[fa] , a[node] , 29) ;//根到节点路径 
	for(int j = 1;(1 << j) < dep[node];++j) f[node][j] = f[f[node][j - 1]][j - 1];
	for(int i = head[node];i;i = edge[i].next) if(edge[i].to != fa) dfs(edge[i].to , node) ;
	tim[node] = dfc ;
}

inline int LCA(int x , int y){
	if(dep[x] < dep[y]) 	swap(x , y) ;
	for(int d = dep[x] - dep[y] ,j = 0;d;d >>= 1 ,++j) if(d & 1) x = f[x][j] ;//奇怪的知识又增加了？？？ 
	if (x == y) return x ;
	for (int j = 16;j >= 0; --j) if(f[x][j] != f[y][j]) x = f[x][j] ,y = f[y][j] ;
	return f[x][0] ;
}

inline int query(int root1 , int root2 , int x , int j){//大节点 小节点 
	if(j == -1)	return 0 ;//到头 
	int p = (x >> j & 1) ^ 1 ;//这一位取反 贪心操作 
	if(siz[ch[root1][p]] - siz[ch[root2][p]])//存在合法点 
		return query(ch[root1][p] , ch[root2][p] , x , j - 1) | 1 << j ;
//存在贡献：如果原来是0 异或成1 那么结果为1 用按位或补成1  反之 原来1 异或0 变成1 不需要补1 最后移动到第j位 
//第j位需要连续移动来确保每一位都有2^j构成   注意按位或操作优先级小于位移！	
	return query(ch[root1][p ^ 1] , ch[root2][p ^ 1] , x , j - 1) ;//没有新的贡献 
}

int main(){
	scanf("%d%d" , &n , &q) ;
	for(int i = 1;i <= n;++i)	scanf("%d" , a + i) ;
	for(int i = 1;i < n;++i){
		int x ,y ;
		scanf("%d%d" , &x , &y) ;
		edge_add(x , y) ;
		edge_add(y , x) ;
	}
	dfs(1 , 0) ;
	for (int i = 1;i <= q;++i){
		int opt ,x ,y, z ;
		scanf("%d" , &opt) ;
		if(opt == 1){
			scanf("%d%d" , &x , &z) ;
			printf("%d\n" , query(rt1[tim[x]] , rt1[dfn[x] - 1] , z , 29)) ;
		}else{
			scanf("%d%d%d" , &x , &y , &z) ;
			int w = f[LCA(x, y)][0] ;
			printf("%d\n" , max(query(rt2[x] , rt2[w] , z , 29) , query(rt2[y] , rt2[w] , z , 29))) ;
		}
	}
	return 0 ;
}
/*
由于处理子树询问的时候对每个点都开一个 01trie 显然不现实，所以考虑可持久化 01trie。
2^30 还是 2^29 关系很大 关系到trie有多少层
可持久化01trie空间要开MAXN*(最大二进制位数+5) 
*/