P4551 最长异或路径

考虑下数组的情况如何解决.
求一个区间$[l,r]$使得区间异或和最大.
处理出区间前缀异或和$pre$,区间异或和$xor(l,r)=pr{e}_r\oplus pr{e}_{l-1}$
枚举$r$的$bit$从高到低.同时把之前的$pr{e}_l$按高位到低位建字典树
对于从高到低枚举的$bit$,我们总是希望让它等于1,所以就是走$tr[p][!c]$那条路径
得到的答案就是最优的$pr{e}_l$
现在,问题的对象从数组的路径变成了树上的路径.
考虑处理出每个点异或到根的值$va{l}_i$.因为两个点的最短路径就是$u->lca(u,v)->v$
$lca(u,v)->root$这部分被异或掉了两次.所以$va{l}_i\oplus va{l}_j$就是$i,j$两点路径的异或值.
问题转换为给定$n$个数字$va{l}_i$,求出两个数字$i,j$,使得$va{l}_i\oplus va{l}_j$最大化。
显然这个问题和第一个问题的解决方法一样.

/*
I don't wanna be left behind,Distance was a friend of mine.
Catching breath in a web of lies,I've spent most of my life.
Catching my breath letting it go turning my cheek for the sake of this show
Now that you know this is my life I won't be told what's supposed to be right
Catch my breath no one can hold me back I ain't got time for that.
*/
#include
using namespace std;
const int maxn = 2e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<pii> G[maxn];
ll val[maxn];
void dfs(int u,int fa){
	for(auto [v,w] :G[u]){
		if(v==fa) continue;
		val[v] = w ^ val[u];
		dfs(v,u);
	}
}
int tr[maxn][2];int idx=0;
void insert(int n){
	int p=0;
	for(int i=30;i>=0;i--){
		int c = (n&(1<<i))>0;
		if(!tr[p][c]) tr[p][c] = ++idx;
		p = tr[p][c];
	}
}
int query(int n){
	//在字典树中找到合适路径最大化 x xor n
	int p =0;int ans = 0;
	for(int i=30;i>=0;i--){
		int c = (n&(1<<i))>0;
		if(tr[p][!c]){
			ans+=(1<<i);
			p = tr[p][!c];
		}
		else p = tr[p][c];
	}
	return ans;
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v,w;cin>>u>>v>>w;
		G[u].push_back({v,w});G[v].push_back({u,w});
	}
	dfs(1,0);int ans = 0;
	for(int i=1;i<=n;i++){
		ans = max(ans,query(val[i]));
		insert(val[i]);
	}
	cout<<ans<<"\n";
}

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