找到两个点之间的路权值异或和最大。
将无根树扯成有根树，将根节点到每个叶子节点的路径异或权值处理出来存起来，然后我们可以遍历取max，因为从根节点到两个叶子节点的值异或起来会把中间重复路径的异或权值消去（异或的性质，相同异或为0），所以借助Trie树就可以了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+10; int trie[maxn][2]; int a[maxn],e[maxn],nxt[maxn],h[maxn],c[maxn],tot,cnt,n; void add(int u,int v,int w) { e[cnt]=v,c[cnt]=w,nxt[cnt]=h[u],h[u]=cnt++; } void dfs(int u,int fa,int sum) { a[u] = sum; for(int i=h[u];~i;i=nxt[i]) { int v = e[i]; if(v!=fa) dfs(v,u,sum^c[i]); } } void insert(int x) { int p=0; for(int i=30;~i;i--) { int &s = trie[p][x>>i&1]; if(!s) s = ++tot; p = s; } } int search(int x) { int p = 0,res = 0; for(int i=30;~i;i--) { int s = x>>i&1; if(trie[p][!s]) { res += 1<<i; p = trie[p][!s]; } else { p = trie[p][s]; } } return res; } int main() { cin>>n; memset(h,-1,sizeof(h)); for(int i=1;i<n;i++) { int u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } dfs(0,-1,0); for(int i=1;i<n;i++) insert(a[i]); int ans = 0; for(int i=1;i<n;i++) { ans = max(ans,search(a[i])); } cout<<ans<<endl; }