题目描述

原题来自：POJ 3764

给定一棵 \(n\) 个点的带权树，求树上最长的异或和路径。

输入格式

第一行一个整数 \(n\)，接下来 \(n-1\) 行每行三个整数 \(u,v,w\)，表示 \(u,v\) 之间有一条长度为 \(w\) 的边。

输出格式

输出一行一个整数，表示答案。

样例数据

样例输入

4
1 2 3
2 3 4
2 4 6

样例输出

7

样例解释

最长的异或和路径是 \(1\to 2\to 3\) ，它的长度是 \(3 \bigoplus 4=7\)。

注意：结点下标从 \(1\) 开始到 \(N\)。

注：\(x \bigoplus y\) 表示 \(x\) 与 \(y\) 按位异或。

限制与提示

对于 \(100\%\) 的数据，\(1\le n\le 10^5,1\le u, v \le n,0 \le w < 2^{31}\)