100 #P1954. Pku3764 The xor-longest Path

    ID: 976 传统题 1000ms 512MiB 尝试: 1613 已通过: 518 难度: 5 上传者: 标签>CF1700普及+/提高-异或抵消深度优先搜索异或 Trie最大异或查询按位贪心

Pku3764 The xor-longest Path

题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

4
1 2 3
2 3 4
2 4 6

输出 #1

7

说明/提示

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

数据范围

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