题意
给你一棵 带权树（每个边有一个权值），让你找到树上任意两个节点之间的路径，使得这条路径上所有边权的异或和（XOR）最大，并输出这个最大值。
思路
树上任意两点 u 和 v 之间路径的异或和，等于 u 到根节点的异或和 异或上 v 到根节点的异或和
Why？！
因为从根节点到 u，和从根节点到 v 的路径中，重复的部分（即从根节点到它们最近公共祖先 LCA 的那一段）会被异或两次。而根据异或的性质 a ^ a = 0，这一段就抵消掉了，剩下的正好是 u 到 v 的唯一路径。
转化后的经典问题（最大异或对）P10471 最大异或对 The XOR Largest Pair - 洛谷
现在你手里有一个数组 dis，里面全是整数。你需要找出 dis[i] ^ dis[j] 的最大值。
如果暴力枚举所有数对（O(n^2)），对于 n=100000 的数据必然超时。
接下来我们就需要利用 01-Trie 进行贪心查找
01-Trie 本质上是一棵二叉树，每个节点只有 0 和 1 两个分叉，用来存储数字的二进制位。
-
插入（建树）：将数组 d 中的每个数字，从**高位（第 30 位）到低位（第 0 位）**依次插入 Trie 树中。
-
查询（贪心）：遍历数组 d 中的每个数字 x，在 Trie 树中查找与它异或结果最大的那个数。
-
贪心策略：为了让异或结果最大，高位优先要变成 1。所以对于 x 的当前位 bit，我们优先走 bit ^ 1 的分支（相反方向）。
-
如果有相反分支，说明这一位异或结果是 1，累加到答案中，走过去。
-
如果没有相反分支，只能走相同的分支，这一位异或结果是 0，走过去。
-
记录每次查询结果的最大值，就是最终答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,maxm=1e5*32+5;
struct Trie01{
int ch[maxm][2],tot;
void init(){
for(int i=0;i<=tot;++i) ch[i][0]=ch[i][1]=0;
tot=0;
}
void insert(int x){
int u=0;
for(int i=30;i>=0;--i)
{
int v=(x>>i)&1;
if(!ch[u][v]) ch[u][v]=++tot;
u=ch[u][v];
}
}
int query(int x){
int u=0,res=0;
for(int i=30;i>=0;--i)
{
int v=(x>>i)&1;
if(ch[u][v^1])
{
res|=(1<<i);
u=ch[u][v^1];
}else u=ch[u][v];
}
return res;
}
}trie01;
struct Edge{
int v;ll w;
};
vector<Edge> adj[maxn];
int dis[maxn];
int n;
void dfs(int u,int p)
{
for(auto [v,w]:adj[u])
{
if(v==p) continue;
dis[v]=dis[u]^w;
dfs(v,u);
}
}
void solve()
{
cin>>n;
for(int i=0;i<n-1;++i)
{
int u,v,w;
cin>>u>>v>>w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
dfs(1,0);
trie01.init();
for(int i=1;i<=n;++i) trie01.insert(dis[i]);
int ans=0;
for(int i=1;i<=n;++i)
{
ans=max(ans,trie01.query(dis[i]));
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int ___T=1;
while(___T--) solve();
return 0;
}
|
