如何求出树上的某两个点的最大路径总异或和?
对于树上的两点之间的简单路径，求经过边权值的最大异或和
首先考虑一个点到根节点所经过路径的异或和，可以深搜求出
考虑两点简单路径的异或和，其值一定是两个点分别到根节点的异或和的异或，那么此时我们已知一个点，如果求出另一个点使得两点之间的异或和最大呢？
考虑字典树存取，深搜完之后，将每个点到根节点的异或和都存到字典树中，对于一个点，我们可以直接在字典树上进行查找，按位进行判断，如果存在以ｘ为根节点的儿子，那么就向下一层，直到遍历到叶节点为止，这样一定是最大的异或和，因为这样可以保证从高位向低位尽可能的都异或
例题：例题
对于询问一，我们直接用一个变量记录一下即可
对于询问二，首先思考，如果我们找的另一个点与这个点的经过的边数是偶数，那么很明显的之前的询问一均无效，因为异或和为０，对于偶数，那么就要异或上它，求一下两者最大值
我们在深搜求距离根节点的异或和过程中，还要记录一个深度，也就是深度为奇还是偶，只有这样，我们才能确定两个点的距离的奇偶性，此外，在询问前还要把本节点删掉，防止自己向自己连边
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+10,mod=1e9+7;
int trie[N][2],cnt[N][2];
int tot=0;
int newNode(){
int x=++tot;
trie[x][0]=trie[x][1]=0;
cnt[x][0]=cnt[x][1]=0;
return x;
}
void add(int x,int d,int t=1){
int p=1;
cnt[p][d]+=t;
for(int i=30;i>=1;i--){
int u=(x>>(i-1)&1);
if(!trie[p][u]){
trie[p][u]=newNode();
}
p=trie[p][u];
cnt[p][d]+=t;
}
}
int query(int x,int d){
int p=1;
if(!cnt[p][d]){
return 0;
}
int ans=0;
for(int i=30;i>=1;i--){
int u=(x>>(i-1)&1);
if(cnt[trie[p][u^1]][d]){
ans|=(1<<(i-1));
p=trie[p][u^1];
}
else p=trie[p][u];
}
return ans;
}
void solve(){
int n,m; cin>>n>>m;
vector<pair<int,int>>g[n+1];
for(int i=1;i<n;i++){
int a,b,c; cin>>a>>b>>c;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
vector<int>a(n+1),d(n+1);
function<void(int,int)>dfs;
dfs=[&](int u,int fa)->void{
for(auto now:g[u]){
int x=now.first,w=now.second;
if(x==fa) continue;
d[x]=d[u]^1;
a[x]=a[u]^w;
dfs(x,u);
}
};
dfs(1,0);
tot=0;
newNode();
for(int i=1;i<=n;i++){
add(a[i],d[i]);
}
int w=0;
while(m--){
char op; cin>>op;
if(op=='^'){
int y; cin>>y;
w^=y;
}
else{
int u,x; cin>>u>>x;
add(a[u],d[u],-1);
cout<<max(query(a[u]^x,d[u]),query(a[u]^x^w,d[u]^1))<<" ";
add(a[u],d[u]);
}
}
cout<<'\n';
}
signed main(){
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();
}