给你一颗n个节点的边带权的树，从树上求两点，使得这两点的简单路径的边异或和最大。
多组数据，每组数据的开始是N（N<=100000），接下来N-1行每行包括3个整数u，v，w（0<=u，v<=n-1,0<=w<=231），表示从u到v有一条长w的路径。
我们可以任意取一个根节点，做一遍dfs求出任意节点到根节点的路径的异或和，用数组d来表示。那么对于任意两个节点i与j，它们之间路径的异或和就是d[i]^d[j]，这是因为由于异或的特性，它们之间的公共路径已经被异或掉了。
于是问题就转变成了，求两点的最大异或和，我们注意到题面中给的数据范围（w<=231）,这提示我们把每一个点的d值拆成一串长31的01串，并把没一个节点对应的d值插入trie树种，因为要求最大，我们从高位往低位插入，当我们扫到一个点$A_{i}$的值的时候，我们基于贪心的思想尽量往与$A_{i}$当前这一位相反的方向走，只有当trie树中没有这相反的一位时，我们才走相同的一位。
因为求d数组和插入，查询都是O（n）的，所以总时间复杂度是O（n）。
代码：
#include<iostream> #include<cmath> #include<cstring> using namespace std; typedef long long ll; const int N=100005; ll edge[2*N],d[N],ans; int ver[2*N],nxt[2*N],head[N]; int trie[31*N][2]; int n,tot=1,cnt; void add(int x,int y,ll z){ver[++cnt]=y,edge[cnt]=z,nxt[cnt]=head[x],head[x]=cnt;} void dfs(int x,int fa){ for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(y==fa) continue; d[y]=d[x]^edge[i]; dfs(y,x); } } void insert(int x){ ll k=d[x]; int p=1; for(int i=30;i>=0;--i){ int ch=(k>>i)&1;//从高位往低位插入 if(!trie[p][ch]) trie[p][ch]=++tot; p=trie[p][ch]; } } ll search(int x){ ll k=d[x],sum=0; int p=1; for(int i=30;i>=0;--i){ int ch=(k>>i)&1; if(trie[p][!ch]){//如果相反的一位存在 sum+=pow((double)2,i); p=trie[p][!ch]; }else p=trie[p][ch];//不存在 } return sum; } int main(){ while(scanf("%d",&n)!=EOF){ memset(trie,0,sizeof(trie)); memset(head,0,sizeof(head)); ans=0,cnt=0,tot=1; for(int i=1,u,v;i<n;++i){ ll w; scanf("%d%d%lld",&u,&v,&w); add(u,v,w),add(v,u,w); } dfs(0,-1);//求d数组 for(int i=0;i<n;++i) insert(i); for(int i=0;i<n;++i) ans=max(ans,search(i)); printf("%lld\n",ans); }; return 0; }
[POJ3764] The XOR Longest Path 题解
原文：https://www.cnblogs.com/Asika3912333/p/11728412.html