The XOR-longest Path
不好的阅读体验
Description
原题来自：POJ 3764
给定一棵 n 个点的带权树，求树上最长的异或和路径。
Input Format
第一行一个整数 n，接下来 n−1 行每行三个整数 u,v,w，表示 u,v 之间有一条长度为 w 的边。
Output Format
输出一行一个整数，表示答案。
Sample
样例输入
4
1 2 3
2 3 4
2 4 6样例输出
7
样例解释
最长的异或和路径是 1→2→3
它的长度是
3⨁4=7。
注意：结点下标从 1 开始到 N。
注：x⨁y 表示 x 与 y 按位异或。
Hint
对于 100% 的数据，1 ≤ n ≤ 10^5 , 1 ≤ u,v ≤ n , 0 ≤ w ≤ 2^31;
---------------------------优雅的分界线----------------------------
正片开始
首先首当其冲先想到的是暴力，即两遍dfs跑图，第一遍预处理，第二遍求根到深度最大的叶子节点所有边的异或，求出答案
然而当我们把暴力代码交上去的时候，迎接我们的不是T，而是WA......
为什么会WA呢？
我们再仔细地读一遍题—————— 树上最长的异或和路径
哎呀！
不是从根到叶子节点的最长路，而是最长的异或和路径；
最近犯唐诗真是越来越严重了呀
所以我们考虑 dijk Tire树。
仔细一想，这不就是0-1 Tire树嘛
只要将每个点到根的异或距离预处理一下，然后都存到0-1树里，就跟 P10471 最大异或对 The XOR Largest Pair （0-1树的板子题）一样了啊
然后只要求其中的最大值就行了
最后，代码附上，完结撒花
#include<bits/stdc++.h>
#define int long long
#define Blue_Archive return 0
#define rint register int
using namespace std;
const int N = 5000010;
const int p = 1313131;
const int mod = 1e9 + 7;int n;
int ans;
int val[N];
int cnt;
int son[N][2];//0-1 trie树
int to[N];//前向星
int nxt[N];//前向星
int h[N];//前向星
int w[N];//前向星
int tot = -1;//前向星inline int max(int x,int y)
{return x > y ? x : y;
}inline int min(int x,int y)
{return x < y ? x : y;
}inline void add(int u,int v,int ww)
{nxt[++ tot] = h[u];to[tot] = v;w[tot] = ww;h[u] = tot;
}inline void update(int val,int x)
{for(int i = (1 << 30);i;i >>= 1){bool t = i & val;if(!son[x][t]) son[x][t] = ++ cnt;x = son[x][t];}
}inline int Shiroko(int val,int x)
{int ans = 0;for(int i = (1 << 30);i;i >>= 1){bool t = i & val;if(!son[x][!t]) {x = son[x][t];}else{x = son[x][!t];ans += i;}}return ans;
}inline void Hoshino(int x,int f)
{for(int i = h[x];~i;i = nxt[i]){int v = to[i];if(v == f) continue;val[v] = val[x] ^ w[i];Hoshino(v,x);}
}// inline void hifumi(int x,int dp)
// {
// if(dp > 1) ans ^= val[x];
// else ans = val[x];
// if(fa[x]) hifumi(fa[x],dp + 1);
// else return;
// }signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(h,-1,sizeof(h));cin >> n;// cnt = 1;for(int i = 1,u,v,ww;i < n;i ++){cin >> u >> v >> ww;add(u,v,ww);add(v,u,ww);}Hoshino(1,-1);for(int i = 1;i <= n;i ++){update(val[i],0);}ans = 0;for(int i = 1;i <= n;i ++){ans = max(ans,Shiroko(val[i],0));}cout << ans << "\n";Blue_Archive;
}
/////////////////////////////
// Shiroko //
/////////////////////////////