该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

0x10基本数据结构（0x16 Trie）最长异或路径

P4551 最长异或路径

题目描述

给定一棵 $n$ 个点的带权树，结点下标从 $0$ 开始到 $n-1$。求树中所有异或路径的最大值。

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

输入格式

第一行一个整数 $n$，表示结点数。

接下来 $n-1$ 行，给出 $u,v,w$ ，分别表示树上的 $u$ 点和 $v$ 点有连边，边的权值是 $w$。

输出格式

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

输入输出样例 #1

输入 #1

4
0 1 3
1 2 4
1 3 6

输出 #1

7

说明/提示

当两个结点分别是 $1,3$ 时，答案是 $7=3\oplus 4$，取最大值。

数据范围

$1\le n \le 100000;0 < u,v \le n;0 \le w < 2^{31}$。