3376 - 最长异或路径
时间限制 : 1 秒
内存限制 : 512 MB
给定一棵 n 个点的带权树,结点下标从 1 开始到 n。寻找树中找两个结点,求最长 的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入
第一行一个整数 n,表示点数。
接下来 n − 1 行,给出 u, v , w ,分别表示树上的 u 点和 v 点有连边,边的权值是 w。
输出
一行, 一个整数表示答案。
样例
输入
4 1 2 3 2 3 4 2 4 6
输出
7
提示
样例解释
最长1,2,4路径的异或值为5,3 xor 6,二进制为101转换为十进制为5;
最长异或序列 1, 2, 3,答案是 7,3 xor 4,二进制为111转换为十进制为7。
【数据范围】
1 ≤ n ≤ 100000; 0 < u, v ≤ n; 0 ≤ w < 231。