题目描述
给定一棵n个点的带权树，求树上最长的异或和路径
输入
The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node u and v of length w.
输出
For each test case output the xor-length of the xor-longest path.
样例输入
4 1 2 3 2 3 4 2 4 6
样例输出
7
题解
Trie树
由于x^x=0，所以树上x和y之间路径的异或和 = x到根路径的异或和 xor y到根路径的异或和。
所以我们先对整棵树进行dfs，求出每个节点到根的路径异或和dis，并加入到Trie树。
然后枚举树上的节点，在Trie树中贪心查询与它异或和最大的数，并加到答案中即可。
#include#include #define N 100010using namespace std;int head[N] , to[N << 1] , len[N << 1] , next[N << 1] , cnt , v[N] , c[N * 30][2] , tot;void add(int x , int y , int z){ to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;}void dfs(int x , int fa){ int i; for(i = head[x] ; i ; i = next[i]) if(to[i] != fa) v[to[i]] = v[x] ^ len[i] , dfs(to[i] , x);}void insert(int x){ int i , p = 0; bool t; for(i = 1 << 30 ; i ; i >>= 1) { t = x & i; if(!c[p][t]) c[p][t] = ++tot; p = c[p][t]; }}int query(int x){ int i , p = 0 , ans = 0; bool t; for(i = 1 << 30 ; i ; i >>= 1) { t = x & i; if(c[p][t ^ 1]) ans += i , p = c[p][t ^ 1]; else p = c[p][t]; } return ans;}int main(){ int n , i , x , y , z , ans = 0; scanf("%d" , &n); for(i = 1 ; i < n ; i ++ ) scanf("%d%d%d" , &x , &y , &z) , add(x , y , z) , add(y , x , z); dfs(1 , 0); for(i = 1 ; i <= n ; i ++ ) insert(v[i]); for(i = 1 ; i <= n ; i ++ ) ans = max(ans , query(v[i])); printf("%d\n" , ans); return 0;}