温馨提示：请先做 Acwing143.最大异或对再做本题（逃
刚刚学的Trie，被这道题卡了1h
题意
给定一个树，树上的边都具有权值。
树中一条路径的异或长度被定义为路径上所有边的权值的异或和
算法分析

1.小问题
不妨先解决这样的一个问题：
给定一个树，树上的边都具有权值。
求给定两点u和v之间路径上所有边的权值的异或和

这个问题很简单，设$Xor_i$为$i$到根节点路径的异或和，只需要简单dfs就可以解决。由于这棵树是无根树，所以从任意一个节点dfs就可以：

void dfs(int now,int t){//now为当前的节点，t为上一层的节点
    for(int i = head[now] ; i != -1 ; i = nxt[i]){//链式前向星
        if(to[i] == t)continue;//避免重复搜索
        Xor[to[i]] = Xor[now]^dis[i];//处理异或值
        dfs(to[i],now);
    }
}

接下来怎样处理呢？
第一感是求出u和v的LCA，设其为t，则答案是(Xor[u] ^ Xor[t]) ^ (Xor[t] ^ Xor[v])
发现这个式子实际上等于(Xor[u] ^ Xor[v]) ^ (Xor[t] ^ Xor[t]) = (Xor[u] ^ Xor[v]) ^ 0 = Xor[u] ^ Xor[v]
LCA可以滚开了
这其实是luogu上的一个问题 luogu P2420让我们异或吧

2.本题
刚才我们解决了任意两点间路径的异或和，现在是求一个最大值。也就是说……
诶？这不就是找两个数，使它们的异或值最大吗？最大异或对？这不是acwing143吗？
Bingo!
完整代码

#include<iostream>
#include<cstdio>

using namespace std;

int n,m,u,v,w,Xor[100010],ans = -1;
int siz,head[100010],to[200010],nxt[200010],dis[200010];//存双向边一定要开2倍空间啊~~
int trie[3100010][2],idx;
int read(){//快读万岁！
    int n = 0,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        n = (n << 3) + (n << 1) + (ch ^ 48);
        ch = getchar();
    }
    return n * f;
}
void add_edge(int f,int t,int d){//链式前向星存储
    dis[++siz] = d;
    to[siz] = t;
    nxt[siz] = head[f];
    head[f] = siz;
}
void dfs(int now,int t){//dfs处理每个节点的Xor
    for(int i = head[now] ; i != -1 ; i = nxt[i]){
        if(to[i] == t)continue;
        Xor[to[i]] = Xor[now]^dis[i]; 
        dfs(to[i],now);
    }
}
void insert(int x){//trie的插入
    int p = 0,t;
    for(int i = 30 ; i >= 0 ; i --){
        t = x >> i & 1;
        if(!trie[p][t])trie[p][t] = ++idx;
        p = trie[p][t];
    }
}
int query(int x){//trie的查询
    int p = 0,t,tans = 0;
    for(int i = 30 ; i >= 0 ; i --){
        t = x >> i & 1;
        tans <<= 1;
        if(trie[p][!t]){
            tans++;
            p = trie[p][!t];
        }
        else p = trie[p][t];
    }
    return tans;
}
int main(){
    n = read();
    for(int i = 1 ; i <= 2*n ; i ++)head[i] = -1;
    for(int i = 1 ; i <= n-1 ; i ++){
        u = read();v = read();w =read();
        u++;v++;//这里比较坑，题目中节点编号是从0开始的，所以要把节点编号都加上1，对答案无影响
        add_edge(u,v,w);
        add_edge(v,u,w);//一定要记得存双向边啊~~
    }
    dfs(1,0);
    for(int i = 0 ;i <= n ; i ++){//跟acwing143一样
        insert(Xor[i]);
        ans = max(ans,query(Xor[i]));
    }
    printf("%d",ans);
    return 0;
}