POJ 3764 The xor-longest Path(字典树)

题目大意

给定一棵 $N$ 个点的赋权树,要求异或和最大的路径。输出最大异或和。
$(1 \le n \le 10^5, 0 \le w \le 2^{31})$

解题思路

字典树 + 贪心

首先由于是一棵树,也即点两两之间的路径使唯一的。

接着考虑异或的性质,异或运算满足交换律、结合律。由此得:

  • $(x \oplus y) \oplus y = x \oplus (y \oplus y) = x$,
  • $(x \oplus a) \oplus (y \oplus a) = x \oplus y$ 。

因此,对于两点 $x,y$ 之间路径的异或和,会等于 $x$ 到另外一个节点 $a$ 的异或和 与 $y$ 到 $a$ 的异或和的异或。

因此先以任意点作为根节点dfs,得到每个点到根节点的异或和。这样问题就转化为“给定 $N$ 个数,求两两之间的最大异或值”。对于本题显然 $O(N^2)$ 是过不了的,而如果使用字典树便可以在 $O(N * 32)$ 接近 $O(N)$ 的时间得到答案。

由于权值 $w \le 2^{31}$,对于求异或有效位只有31位,我们对于每个数从高位向低位建树,将所有的异或值保存起来。然后询问时尽量(贪心)走相反的路径(使该位异或为 $1$),使得最大异或和尽量大。

解题代码

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
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MAXM = 1e6;
const int MAXS = 2;

struct Edge {
int to, cost, next;
Edge( int to = 0, int cost = 0, int next = 0 ) : to(to), cost(cost), next(next) {}
} G[MAXN << 1];
int n;
int tot, head[MAXN];
int dp[MAXN];

struct Trie {
int cnt, sz[MAXN * 32][MAXS];
void init() {
cnt = 0;
sz[0][0] = sz[0][1] = 0;
}
void insert(int va) {
int now = 0;
for( int i = 30; i >= 0; -- i ) {
int index = va >> i & 1;
if( !sz[now][index] ) {
sz[now][index] = ++cnt;
sz[cnt][0] = sz[cnt][1] = 0;
}
now = sz[now][index];
}
}
int query(int va) {
int now = 0, ans = 0;
for( int i = 30; i >= 0; -- i ) {
int index = !(va >> i & 1);
if( sz[now][index] ) {
ans |= 1 << i;
now = sz[now][index];
}
else {
now = sz[now][!index];
}
}
return ans;
}
} T;

void init()
{

tot = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int cost)
{

G[tot] = Edge(v, cost, head[u]);
head[u] = tot++;
G[tot] = Edge(u, cost, head[v]);
head[v] = tot++;
}
void dfs(int u, int pre, int xo)
{

dp[u] = xo;
for( int i = head[u]; ~i; i = G[i].next ) {
Edge &e = G[i];
if( e.to == pre ) continue;
dfs(e.to, u, xo ^ e.cost);
}
}
int main()
{

while( ~scanf("%d", &n) ) {
init();
int u, v, w;
for( int i = 0; i < n - 1; ++ i ) {
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
}
dfs(0, -1, 0);
T.init();
int Max = 0;
for( int i = 0; i < n; ++ i ) {
Max = max(Max, T.query(dp[i]));
T.insert(dp[i]);
}
printf("%d\n", Max);
}
return 0;
}

解题总结

  1. RE了好多发…后来发现是第30行写搓了,写成了 int index = v & (1 << i); …以后统一换成这种写法: v >> i & 1。
  2. 要学会判断字典树数组要开多大。
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!