P4551 最长异或路径

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

/*
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 pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector 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=0;i--){
		int c = (n&(1u>>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