4398: 最长异或值路径

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:Special Judge 上传者:
提交:10 通过:6

题目描述

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

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

formula.png

 为异或符号。

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

输入格式

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

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

输出格式

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

输入样例 复制

4
0 1 3
1 2 4
1 3 6

输出样例 复制

7

数据范围与提示

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


1≤n≤100000,
0≤u,v<n,
0≤w<231