P4551最长异或路径|01trie

01踹树是个好东西……

P4551 最长异或路径

题目描述

给定一棵n个点的带权树,结点下标从1开始到N。寻找树中找两个结点,求最长的异或路径。

异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入输出格式

输入格式:

第一行一个整数N,表示点数。

接下来 n−1 行,给出 u,v,w,分别表示树上的 u 点和 v 点有连边,边的权值是 w。

输出格式:

一行,一个整数表示答案。

输入输出样例

输入样例#1:

1
2
3
4
4
1 2 3
2 3 4
2 4 6

输出样例#1:

1
7

说明

最长异或序列是1-2-3,答案是 7 (=3 ⊕ 4)

数据范围

$1≤n≤100000;$ $0<u,v≤n;$ $0≤w<2^31$


关于最大异或值,往往可以用 线性基 贪心 去做

对于当前的一个01串,从高到低考虑是否存在一个与当前位置异或为1的另一个串。显然异或后最高位越大,整个值就越大。

从高到低,找不同,这个东西很像trie树对不对,只不过普通trie树中存的是字符,这里我们要用到的是01trie(即只含01的trie)。

首先trie的存储方式是在边中存储,所以我们需要考虑如何将点权化为边权。点权化边权,最常用的方法就是前缀和。显然对于这道题,我们可以遍历一遍整棵树,处理出根节点到每个节点的异或前缀和。然后我们将所有点的异或前缀和插入到trie树中就行了。

对于两个结点之间唯一路径上的所有边权的异或,这两个节点的位置关系有两种情况:一是祖先与子节点,另一种是兄弟关系。对于第一种情况,祖先之前的边在前缀和中计算了两次,因为$x~xor~x = 0$,所以两者的前缀和相异或即可。对于第二种情况呢?其实是一样的,他们的LCA到根节点的边计算了两次,异或相消,即为答案。

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
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 0x7fffffff;
const int MAXN = 100010;
int N;
int trie[MAXN << 5][2], xo[MAXN], ans, root;

struct Edge {
int nxt, to, val;
}e[MAXN << 1];

template <typename _Tp>
inline void read(_Tp &x) {
char ch = getchar( ); bool f = 0; x = 0;
while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar( ); }
while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar( ); }
x = f ? -x : x;
}

int head[MAXN], tot;
void AddEdge(int x, int y, int w) {
e[++ tot].to = y, e[tot].val = w, e[tot].nxt = head[x], head[x] = tot;
}

void Build(int x, int rt) {
for (int i = 1 << 30; i; i >>= 1) {
bool id = i & x;
if (!trie[rt][id]) trie[rt][id] = ++ tot;
rt = trie[rt][id];
}
}

int Query(int x, int rt) {
int ans = 0;
for (int i = 1 << 30; i; i >>= 1) {
bool id = i & x;
if (trie[rt][id ^ 1]) {
ans += i;
rt = trie[rt][id ^ 1];
}
else rt = trie[rt][id];
} return ans;
}

void Init(int u, int f) {
for (int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (v == f) continue;
xo[v] = xo[u] ^ e[i].val;
Init(v, u);
}
}

int main( ) {
read(N);
int u, v, w;
for (int i = 1; i < N; ++ i) {
read(u), read(v), read(w);
AddEdge(u, v, w);
AddEdge(v, u, w);
}
Init(1, 0);
for (int i = 1; i <= N; ++ i) Build(xo[i], root);
int ans = -INF;
for (int i = 1; i <= N; ++ i)
ans = max(ans, Query(xo[i], root));
printf("%d\n", ans);
return 0;
}
{% if theme.fireworks %} {% endif %} {{ live2d() }}