#P4551. 最长异或路径

最长异或路径

题目描述

给定一棵 nn 个点的带权树,结点下标从 11 开始到 nn。寻找树中找两个结点,求最长的异或路径。

异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入格式

第一行一个整数 nn,表示点数。

接下来 n1n-1 行,给出 u,v,wu,v,w ,分别表示树上的 uu 点和 vv 点有连边,边的权值是 ww

输出格式

一行,一个整数表示答案。

4
1 2 3
2 3 4
2 4 6
7

提示

最长异或序列是 1,2,31,2,3,答案是 7=347=3\oplus 4

数据范围

1n100000;0<u,vn;0w<2311\le n \le 100000;0 < u,v \le n;0 \le w < 2^{31}