7.22
2026-07-22 17:34:54
发布于：广东
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
// ====================== 数据结构定义 ======================
// 邻接表的边结构体：只保留基础成员，无构造函数
struct {
int to; // 边的终点
int w; // 边的权值
};
// 邻接表：g<Edge>raph[u]存储u的所有邻边（vector实现）
vector graph[200010];
// sum[u]：根节点(1号)到u的路径异或和
int sum[200010];
// 01字典树结构
struct TrieNode {
int ch[2];
} trie[200010 * 32];
int tot = 0; // 字典树节点计数器
// ====================== 函数定义 ======================
// DFS预处理：计算每个节点到根的异或和（替换auto为下标遍历）
void dfs(int u, int fa) {
// 常规下标遍历：i从0到graph[u]的元素个数-1
for (int i = 0; i < graph[u].size(); ++i) {
// 取第i个邻边（替代auto& edge）
Edge edge = graph[u][i];
int v = edge.to; // 邻边终点
int w = edge.w; // 边权
if (v == fa) continue; // 跳过父节点
sum[v] = sum[u] ^ w; // 更新根到v的异或和
dfs(v, u); // 递归遍历子节点
}
}
// 01字典树插入
//trie[x].ch[0] 代表当前节点 x 下一位是 0 的路径通向哪个节点；
//trie[x].ch[1] 代表下一位是 1 的路径。
void build(int val, int x) {
// 从二进制的最高位(230)开始，逐位向左移动直到最后一位(20)
for (int i = (1 << 30); i; i >>= 1) {
bool c = val & i; // 取出 val 的当前二进制位（是0还是1）
// 如果当前节点下面没有这条分支（0或1）
if (!trie[x].ch[c]) {
trie[x].ch[c] = ++tot; // 创建一个新节点（编号++tot）
}
x = trie[x].ch[c]; // 顺着这条分支向下走，更新当前节点位置
}
}
// 01字典树查询
//在二进制异或运算中，0 ^ 1 = 1，1 ^ 0 = 1。
//只有当前位两个数不同，异或结果才是 1。
//为了找到最大异或结果，我们永远优先让更高位的异或结果变成 1。
int query(int val, int x) {
int ans = 0;
// 同样从最高位(2^30)开始遍历到最低位
for (int i = (1 << 30); i; i >>= 1) {
bool c = val & i; // 取出 val 的当前二进制位
// 核心贪心策略：为了异或结果最大，当前位尽量为 1
// 如果存在相反的数字分支 (!c)
if (trie[x].ch[!c]) {
ans += i; // 异或结果当前位是1，答案加上当前位的权值 i
x = trie[x].ch[!c]; // 走到相反的数字分支
} else {
// 如果没有相反的分支，只能被迫走相同的数字分支
x = trie[x].ch[c];
// 因为相同相异或等于0，所以 ans 不需要加上当前位权值 i
}
}
return ans;
}
// ====================== 主函数 ======================
int main() {
//加快cin cout 的运行速度
//写完之后不可使用printf 和 scanf
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// 读入n-1条边，构建邻接表（无构造函数，手动赋值）
for (int i = 1; i <= n - 1; ++i) {
int u, v, w;
cin >> u >> v >> w;
// 方式1：先创建空Edge，再赋值（最基础）
Edge e1;
e1.to = v;
e1.w = w;
graph[u].push_back(e1); // u->v的边
Edge e2;
e2.to = u;
e2.w = w;
graph[v].push_back(e2); // v->u的边
}
// 预处理根到所有节点的异或和
dfs(1, -1);
// 插入所有异或和到字典树
for (int i = 1; i <= n; ++i) {
build(sum[i], 0);
}
// 查询最大异或值
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, query(sum[i], 0));
}
cout << ans << endl;
return 0;
}
这里空空如也
有帮助，赞一个