Description

[POJ3764]

给定一个树，树上的边都具有权值。

树中一条路径的异或长度被定义为路径上所有边的权值的异或和：

$_{xor}length(p)=\oplus_{e\in{p}}w(e)$

⊕ 为异或符号。

给定上述的具有n个节点的树，你能找到异或长度最大的路径吗？

Input Format

第一行包含整数n，表示树的节点数目。

接下来n-1行，每行包括三个整数u，v，w，表示节点u和节点v之间有一条边权重为w。

数据规模：

1 ≤ n ≤ 100000,

0 ≤ u,v < n

0 ≤ w < 2^31## Output Format

输出一个整数，表示异或长度最大的路径的最大异或和。

4
0 1 3
1 2 4
1 3 6​

7​

Hint

样例中最长异或值路径应为0->1->2,值为7 (=3 ⊕ 4)

Source

Trie