P4592 [TJOI2018]异或

有一颗以 \(1\) 为根节点的由 \(n\) 个节点组成的树，节点从 \(1\) 至 \(n\) 编号。树上每个节点上都有一个权值 \(v_i\)。现在有 \(q\) 次操作，操作如下：

• \(1~x~z\)：查询节点 \(x\) 的子树中的节点权值与 \(z\) 异或结果的最大值。
• \(2~x~y~z\)：查询节点 \(x\) 到节点 \(y\) 的简单路径上的节点的权值与 \(z\) 异或结果最大值。

\(1< n, q \leq10^5\)，\(1 \leq u, v, x, y \leq n\)，\(1 \leq op \leq 2\)，\(1 \leq v_i, z \lt 2^{30}\)。

先解释一下选择树剖的原因，题目给了两种操作都和树剖得到的顺序有关，方便用可持久化Trie实现。然后在树剖后的新顺序下进行可持久化插入，然后进行查询。对于子树进行一次操作即可，对于两点间进行不超过 \(logn\) 次操作，还是很优的。

#include<bits/stdc++.h>


int pv[100005],n,m,pv1[100005];
namespace PresidentTrie{
	int trie[30000000][2],tcnt,root[100005],latest[30000000];
	void insert(int dep,int p,int q,int i){
		if(dep<0){
			latest[q]=i;
			return;
		}
		int c=(pv[i]>>dep)&1;
		if(p)
			trie[q][c^1]=trie[p][c^1];
		trie[q][c]=++tcnt;
		insert(dep-1,trie[p][c],trie[q][c],i);
		latest[q]=std::max(latest[trie[q][0]],latest[trie[q][1]]);
	}
	int query(int num,int p,int dep,int L){
		if(dep<0)
			return pv[latest[p]]^num;
		int c=(num>>dep)&1;
		if(latest[trie[p][c^1]]>=L){
			return query(num,trie[p][c^1],dep-1,L);
		}
		else return query(num,trie[p][c],dep-1,L);
	}
}

namespace TreeChain{
	struct node{
		int fa,son,sz,dep,val,top,to;
	}nd[100005];
	struct edge{
		int to,nxt;
	}e[200005];
	int head[100005],ecnt,ncnt;
	inline void adde(int u,int v){
		e[++ecnt].nxt=head[u];
		e[ecnt].to=v;
		head[u]=ecnt;
	}
	void dfs1(int x,int fa){
		nd[x].dep=nd[fa].dep+1;
		nd[x].fa=fa;
		nd[x].sz=1;
		int mx=-1;
		for(int i=head[x];i;i=e[i].nxt){
			int y=e[i].to;
			if(y==fa)
				continue;
			dfs1(y,x);
			nd[x].sz+=nd[y].sz;
			if(nd[y].sz>mx){
				nd[x].son=y;
				mx=nd[x].sz;
			}
		}
	}
	void dfs2(int x,int top){
		nd[x].to=++ncnt;
		pv[ncnt]=pv1[x];
		nd[x].top=top;
		if(nd[x].son)
			dfs2(nd[x].son,top);
		for(int i=head[x];i;i=e[i].nxt){
			int y=e[i].to;
			if(nd[x].fa==y || nd[x].son==y)
				continue;
			dfs2(y,y);
		}
	}
}

using namespace TreeChain;
using namespace PresidentTrie;

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&pv1[i]);
	}
	for(int i=1;i<n;++i){
		int u,v;
		scanf("%d %d",&u,&v);
		adde(u,v);
		adde(v,u);
	}
	dfs1(1,1);
	dfs2(1,1);
	root[0]=++tcnt;
	for(int i=1;i<=n;++i){
		root[i]=++tcnt;
		insert(30,root[i-1],root[i],i);
	}
	while(m--){
		int op,x,y,z;
		scanf("%d",&op);
		if(op==1){
			scanf("%d %d",&x,&z);
			printf("%d\n",query(z,root[nd[x].sz+nd[x].to-1],30,nd[x].to));
		}
		if(op==2){
			int ans=0;
			scanf("%d %d %d",&x,&y,&z);
			while(nd[x].top!=nd[y].top){
				if(nd[nd[x].top].dep<nd[nd[y].top].dep)
					std::swap(x,y);
				ans=std::max(ans,query(z,root[nd[x].to],30,nd[nd[x].top].to));
				x=nd[nd[x].top].fa;
			}
			if(nd[x].dep<nd[y].dep){
				std::swap(x,y);
			}
			ans=std::max(ans,query(z,root[nd[x].to],30,nd[y].to));
			printf("%d\n",ans);
		}
	}
	return 0;
}