给定一棵n个点的带权树，结点下标从1开始到N。寻找树中找两个结点，求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
第一行一个整数N，表示点数。
接下来 n-1行，给出 u,v,w，分别表示树上的u点和v点有连边，边的权值是w。
输出格式：一行，一个整数表示答案。
4 1 2 3 2 3 4 2 4 6
7
最长异或序列是1-2-3，答案是 7 (=3 ⊕ 4)
1≤n≤100000;0<u,v≤n;0≤w<231
用d[i]表示从根到i的边权xor和
则d[to]=d[u] xor val(u,to)
可知两个结点之间唯一路径xor和为d[x] xor d[y]（两路径重合部分消掉：a^a=0）
则转换为求二元组使xor和最大
构造01trie，贪心取值
#include<bits/stdc++.h> using namespace std; const int maxn=100000+100; int ch[maxn<<5][2]; long long d[maxn],mark[maxn]; long long ans=0; int head[maxn]; int tot=1,size=0; struct edge { int to,next; long long val; }e[maxn<<1]; void addedge(int u,int v,long long w) { e[++size].to=v;e[size].val=w;e[size].next=head[u];head[u]=size; } inline long long read() { long long x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar(); } return x*f; } void insert(int x) { int now=0; for(int i=31;i>=0;i--) { bool id=x&(1ll<<i); if(!ch[now][id])ch[now][id]=++tot; now=ch[now][id]; } } long long serch(long long x) { int now=0; long long ans=0; for(int i=31;i>=0;i--) { bool id=x&(1ll<<i); if(ch[now][id^1])ans+=(1ll<<i),now=ch[now][id^1]; else now=ch[now][id]; } return ans; } void dfs(int u,int fa) { for(int i=head[u];i;i=e[i].next) { int to=e[i].to; if(to==fa)continue; d[to]=d[u]^e[i].val; dfs(to,u); } } int main() { int n=read(); for(int i=1;i<n;i++) { long long u=read(),v=read(),w=read(); addedge(u,v,w); addedge(v,u,w); } dfs(1,0); for(int i=1;i<=n;i++) insert(d[i]); for(int i=1;i<=n;i++) ans=max(ans,serch(d[i])); printf("%lld",ans); return 0; }
原文：https://www.cnblogs.com/DriverBen/p/10918783.html
