题意
给出一棵有权树,定义一个路径的权值为这条路径上所有边权的异或和。
请求出最大的路径权值。
思路
想着想着突然发现从任意一个节点 \(rt\) 开始dfs,对于每个节点 \(u_i\) 可以得到 rt---> \(u_i\) 这条路径的权值\(val_i\)。
这时我们任意选择两个节点 \(u,v\),可以发现 \(val_{u}\ xor\ val_{v}\) 就是 \(u\) 到 \(v\) 的路径权值。
这时题目就转化成了,给出 N 个数字求两个数字的最大异或和。
就跟【算法竞赛进阶指南】字典树 The XOR Largest Pair 一样了。
代码
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <vector>
#define pb push_back
#define pii pair<int, int>
#define pll pair<int, int>
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
using namespace std;
vector<pii> vec[N];
vector<ll> v;
void dfs(int u, int fa, ll now)
{
if (u != fa)
v.pb(now);
for (int i = 0; i < vec[u].size(); i++) {
pll tmp = vec[u][i];
if (tmp.first == fa)
continue;
dfs(tmp.first, u, now ^ tmp.second);
}
}
int s[N], trie[N * 10][2], tot = 1;
void insert()
{
int p = 1;
for (int i = 0; i < 32; i++) {
int now = s[i];
if (!trie[p][now]) {
trie[p][now] = ++tot;
}
p = trie[p][now];
}
}
ll solve()
{
ll ans = 0, p = 1, cnt = 31;
for (int i = 0; i < 32; i++, cnt--) {
int now = 1 ^ s[i];
if (trie[p][now]) {
ans += (1LL << cnt);
} else {
now = s[i];
}
p = trie[p][now];
}
return ans;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
vec[u].pb({ v, w }), vec[v].pb({ u, w });
}
dfs(1, 1, 0);
ll rel = 0;
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < 32; j++) {
s[31 - j] = (v[i] & (1LL << j)) ? 1 : 0;
}
insert();
rel = max(rel, solve());
}
printf("%lld\n", rel);
return 0;
}