【bzoj1954】Pku3764 The xor-longest Path

2014年12月16日2,2510

Description

给定一棵n个点的带权树,求树上最长的异或和路径

Input

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.

Output

For each test case output the xor-length of the xor-longest path.

Sample Input

4
1 2 3
2 3 4
2 4 6

Sample Output

7 

HINT

The xor-longest path is 1->2->3, which has length 7 (=3 ⊕ 4)
注意:结点下标从1开始到N….

题解

求出根到每个结点的边权异或和

问题转换为任选两点,异或和最大

trie的经典?应用

在trie上从插入所有权值,再查询每个权值。。。(从高位到低位)

查询x的时候,每一位尽量走与x该位不同的结点