题目链接：最长异或路径 - 洛谷
题目描述
给定一棵 n 个点的带权树，结点下标从 1 开始到 n。寻找树中找两个结点，求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入格式
第一行一个整数 nn，表示点数。
接下来 n-1n?1 行，给出 u,v,w ，分别表示树上的 u 点和 v 点有连边，边的权值是 w。
输出格式
一行，一个整数表示答案。
输入输出样例
输入 #1复制
4 1 2 3 2 3 4 2 4 6
输出 #1复制
7
题解：
一个数，如果它两次异或同一个数，那么它是不会有改变的。
那么i~j的路径上的异或和，就可以表示成根到i的异或和异或上根到j的异或和。
那思路就很明确了：将根节点到每个节点的路径权值异或和insert到trie里，再在trie里找异或最大值；那么我们在trie中对于每一位进行贪心，从高位到低位，如果这一位有一个与它不同的，即异或 后是1，那我们就顺着这条路往下走；否则就顺着原路往下走。
因为高位决定答案，所以此贪心策略正确；
代码如下：
/*Keep on going Never give up*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi acos(-1.0)
inline int read()
{int x=0,k=1; char c=getchar();while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*k;
}
const int maxn=2e6+10;
int trie[maxn][2],_xors[maxn],n,tot,toot;
int nxt[maxn],edge[maxn],val[maxn],head[maxn];
void _insert(int x){int now=0;for(int i=31;i>=0;i--){bool t=(1&(x>>i));if(!trie[now][t]) trie[now][t]=++toot;now=trie[now][t];}return ;
}
void add(int x,int y,int z){nxt[++tot]=head[x];val[tot]=y;edge[tot]=z;head[x]=tot;
}
void dfs(int x,int fa){ for(int i=head[x];i;i=nxt[i]){int v=val[i],zz=edge[i];if(v!=fa){// printf("%lld -> %lld\n",x,v);_xors[v]=_xors[x]^zz;dfs(v,x);} }return ;
}
int ask(int x){int ans=0,now=0;for(int i=31;i>=0;i--){bool ttt=((x>>i)&1);if(trie[now][(ttt^1)]){ans+=(1<<i);now=trie[now][(ttt^1)];}elsenow=trie[now][ttt];}return ans;
}
signed main(){ n=read();for(int i=1;i<n;i++){int x=read(),y=read(),z=read();add(x,y,z);add(y,x,z);}int res=-11; dfs(1,0);/* for(int i=1;i<=n;i++){cout<<i<<" "<<_xors[i]<<endl;}*/for(int i=1;i<=n;i++)_insert(_xors[i]);for(int i=1;i<=n;i++){res=max(res,ask(_xors[i]));}cout<<res;
}trie和dfs还是要多写啊，不然出错要改好久QwQ