bzoj#P1954. [PKU3764] The xor-longest Path

[PKU3764] The xor-longest Path

题目描述

In an edge-weighted tree, the xor-length of a path pp is defined as the xor sum of the weights of edges on pp:

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

\oplus is the xor operator.

We say a path the xor-longest path if it has the largest xor-length. Given an edge-weighted tree with nn nodes, can you find the xor-longest path?

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

输入格式

The input contains several test cases. The first line of each test case contains an integer nn, The following n1n-1 lines each contains three integers u,v,wu, v, w (0u<n0 \le u \lt n, 0v<n0 \le v \lt n), which means there is an edge between node uu and vv of length ww.

输出格式

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

4
1 2 3
2 3 4
2 4 6
7

样例说明

The xor-longest path is 1231 \to 2 \to 3, which has length 77 (343 \oplus 4).

提示

注意:结点下标从 11 开始到 nn

数据规模与约定

对于 100%100\% 的数据,1n1051 \le n \le 10^50w<2310 \le w \lt 2^{31}