最长异或路径

题目描述

给定一棵 $n$ 个结点的带权树。树上任意两个结点之间都有唯一一条简单路径。

请你找到一条路径，使路径上所有边权的异或和最大，并输出这个最大值。

输入格式

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含三个整数 $u,v,w$，表示一条带权边。

输出格式

输出一个整数，表示最大的路径异或和。

数据范围

$2 \le n \le 10^5$，$0 \le w < 2^{30}$。

来源说明

本题为 CodeCamp 专项训练题，训练方向参考：洛谷 P4551《最长异或路径》。

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含三个整数 $u,v,w$，表示一条带权边。

输出一个整数，表示最大的路径异或和。

$2 \le n \le 10^5$，$0 \le w < 2^{30}$。