「LOJ 10056」The XOR-longest Path

Description

给定一棵 $n\ (1 \leq n \leq 10^5)$ 个点的带权树,求树上最长的异或和路径。$(0 \leq 边权 < 2^{31})$

Source

[LOJ]10056

Solution

$a,b$ 的树上路径异或和其实就是 $a$ 到根的路径异或和 与 $b$ 到根的路径异或和 的异或值。原因是:根据异或运算的性质 $x \oplus x = 0$ 可知,两个点到根重复的路径会互相抵消为 $0$,对答案不影响。

所以我们可以先用 搜索 求出每个点到根的路径异或和,然后把这些值插入到 Trie 中,从中选出两点使其异或和最大,这就和另外一题 [LOJ]10050 一样了,不会的话自行阅读,这里不再赘述过程。

Code

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
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5, MAXM = 2e5;
int n, tot, ans, head[MAXN + 5], val[MAXN + 5];
struct Edge {
int next, to, dis;
} e[MAXM + 5];
struct Trie {
int tot, ch[MAXN * 31 + 5][2];

inline void insert(int x) {
int u = 1;
for (int i = 30; ~i; --i) {
bool v = x & (1 << i);//x 二进制下第 i 位的值
if (!ch[u][v]) ch[u][v] = ++tot;//新建节点
u = ch[u][v];
}
}
inline int find(int x) {
int u = 1, res = 0;
for (int i = 30; ~i; --i) {
bool v = x & (1 << i);//x 二进制下第 i 位的值
if (!ch[u][v ^ 1]) u = ch[u][v];//如果没有相反的路,则沿相同的路走
else {
res += 1 << i;//走相反的路
u = ch[u][v ^ 1];//这一位为 1,累加答案
}
}
return res;
}
} tr;

inline void addEdge(int u, int v, int w) {
e[++tot] = (Edge) { head[u], v, w };
head[u] = tot;
}

void dfs(int u, int fa) {
for (int v, w, i = head[u]; v = e[i].to, w = e[i].dis, i; i = e[i].next) {
if (v == fa) continue;
val[v] = val[u] ^ w;//预处理出每个节点到根的路径异或和
dfs(v, u);
}
}

int main() {
read(n);
for (int u, v, w, i = 1; i < n; ++i) {
read(u), read(v), read(w);
addEdge(u, v, w), addEdge(v, u, w);//连无向边
}
dfs(1, 0);
tr.tot = 1;
for (int i = 1; i <= n; ++i) {
ans = max(ans, tr.find(val[i]));//查找 x 与 Trie 中已有数的异或最大值
tr.insert(val[i]);//把 x 插入到 Trie 中
}
write(ans);
putchar('\n');
return 0;
}

本文标题:「LOJ 10056」The XOR-longest Path

文章作者:Heartlessly

发布时间:2019年05月06日 - 19:01:41

最后更新:2019年05月06日 - 19:24:22

原始链接:https://heartlessly.github.io/problems/loj-10056/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%