给定一棵 n 个点的带权树，求树上最长的异或和路径。
同学考我的一道题
很巧妙，首先我们来兴暴力维护是n^3的，然后从异或的性质来考虑
异或的值是满足前缀和性质的，所以我们只需要枚举两个节点，然后现在的会见复杂度是n^2
然后来兴我们在维护完前缀和之后，只需要选择两个异或之后结果最大的两个前缀和
就正好可以用Trie来维护，时间复杂度就变成了n*31（因为数据在int范围内）
下面给出代码：
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #define register int int using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘; return x*f; } inline int max(int x,int y){return x>y?x:y;} inline void write(int x){ if(x<0) putchar(‘-‘),x=-x; if(x>9) write(x/10); putchar(x%10+‘0‘); return ; } int n; int cnt[200006]; int head[200006]; int nxt[200006],to[200006],dis[200006]; int total=0; inline void add(int x,int y,int z){ total++; to[total]=y; dis[total]=z; nxt[total]=head[x]; head[x]=total; return ; } int sum[200006]; inline void dfs(int x,int fa){ for(int e=head[x];e;e=nxt[e]){ if(to[e]!=fa&&!sum[to[e]]){ sum[to[e]]=sum[x]^dis[e]; dfs(to[e],x); } } return ; } int a[32]; int trie[3200006][2]; int tot=1; inline void build(int len){ int c=1; for(int i=32;i>=1;i--){ if(!trie[c][a[i]]) trie[c][a[i]]=++tot; c=trie[c][a[i]]; } return ; } int p[100006]; inline int solve(int len){ int c=1,num=0; for(int i=32;i>=1;i--){ if(trie[c][!a[i]]){ c=trie[c][!a[i]]; num+=p[i-1]; } else c=trie[c][a[i]]; } return num; } int main(){ p[0]=1; for(int i=1;i<=31;i++) p[i]=p[i-1]*2; n=rd(); for(int i=1;i<n;i++){ int x=rd(),y=rd(),z=rd(); add(x,y,z); } dfs(1,-1); for(int i=1;i<=n;i++){ memset(a,0,sizeof(a)); int h=sum[i]; int pos=0; while(h){ a[++pos]=h%2; h>>=1; } build(pos); } int ans=0; for(int i=1;i<=n;i++){ memset(a,0,sizeof(a)); int h=sum[i]; int pos=0; while(h){ a[++pos]=h%2; h>>=1; } ans=max(ans,solve(pos)); } write(ans); return 0; }
原文：https://www.cnblogs.com/WWHHTT/p/9891006.html