【字典树】洛谷 P4551 最长异或路径
2021-10-15 13:12:00 # ACM

题链

题目解析

树上每条边都有一个权值，求最大异或路径的值；

以 $1$ 为根，求 $i \in [1,n]$ 到 $1$ 的异或路径的值，对这些值建立 $01$ 字典树，对于每个值都在这颗字典树上查找与之异或最大的数即可；

代码实现

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 <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
#include <cstring>
#include <stack>
using namespace std;
	#define ls rt<<1
	#define rs rt<<1|1
	#define LL long long
	#define ll long long
	#define ULL unsigned long long
	#define MAXN 2e9
	#define mod 1000000007
	#define MS 100009

int n,m,k;
struct node{
	int poi,val;
};
vector<node > vc[MS];
int sum[MS];
int dir[MS*30][2], tot;

void dfs(int u,int f){
	for (auto v:vc[u]){
		if (v.poi != f){
			sum[v.poi] = sum[u]^v.val;
			dfs(v.poi,u);
		}
	}
}

void insert(int x){
	for (int i=30,u=0;i>=0;i--){
		int t = (x>>i)&1;
		if (!dir[u][t]) dir[u][t] = ++tot;
		u = dir[u][t];
	}
}

int query(int x){
	int ans = 0;
	for (int i=30,u=0;i>=0;i--){
		int t = (x>>i)&1;
		if (dir[u][t^1]){
			ans += (1<<i);
			u = dir[u][t^1];
		}
		else {
			u = dir[u][t];
		}
	}
	return ans;
}

void solve(){
	cin >> n;
	for (int i=2;i<=n;i++){
		int u,v,w; cin >> u >> v >> w;
		vc[u].push_back({v,w});
		vc[v].push_back({u,w});
	}
	dfs(1,0);
	int ans = 0;
	for (int i=1;i<=n;i++) insert(sum[i]);
	for (int i=1;i<=n;i++) ans = max(ans,query(sum[i]));
	cout << ans << "\n";
}

int main(){
	ios::sync_with_stdio( false );
	int ce = 1;
	//cin >> ce;
	while (ce--) solve();
	return 0;
}
Prev
2021-10-15 13:12:00 # ACM
Next