『MdOI R1』Path

题目描述

给定一棵 $n$ 个点的无根树,边有边权。 令 $V(x,y),E(x,y)$ 分别表示树上 $x,y$ 之间的简单路径上的所有点的集合和所有边的集合,特别地,当 $x=y$ 时,$V(x,y) = \{x\}$,$E(x,y) = \varnothing$。 再令边集 $E$ 的权值 $f(E)$ 为 $E$ 中所有边的权值的 **异或和**,当 $E = \varnothing$ 时,$f(E) = 0$。 现在,要你求出 $$ \max_{1\le x,y,u,v \le n,V(x,y)\cap V(u,v) = \varnothing}(f(E(x,y)) + f(E(u,v))) $$ 通俗的讲,你要选择两条简单路径,满足没有重合的点,且边权异或和之和最大。

输入输出格式

输入格式


第一行一个整数 $n$,表示树上点的个数。 接下来 $n-1$ 行,每行三个整数 $x,y,w$,表示编号为 $x$ 和 $y$ 的点之间有一条权值为 $w$ 的边。

输出格式


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

输入输出样例

输入样例 #1

9
1 2 1
1 3 7
2 4 8
3 5 3
4 6 3
3 7 3
7 8 5
7 9 2

输出样例 #1

21

输入样例 #2

3
1 2 2
2 3 1

输出样例 #2

2

说明

【样例 1 解释】 样例中的树如图所示,选择标红色和蓝色的两条路径,满足没有重合的点,且边权异或和之和最大,为 $(7\oplus 1\oplus 8)+(5\oplus 2)=21$(其中 $\oplus$ 表示异或运算)。 ![](https://cdn.luogu.com.cn/upload/image_hosting/jen9sxcf.png) 【样例 2 解释】 样例中的树如图所示,为一条链的形状,选择标红色和蓝色的两条路径,蓝色路径退化成了一个点,使异或和之和达到最大值 $2+0=2$。注意红色路径并不能延申到 $3$,否则蓝色路径将无法存在。 ![](https://cdn.luogu.com.cn/upload/image_hosting/1xzo1lh2.png) --- 【数据范围】 **本题采用捆绑测试。** | 子任务编号 | $n\leq$ | 特殊性质 | 分值 | 时限 | | :--------: | :------------: | :---------: | :--: | :--: | | 1 | $50$ | 无 | 12 | 1s | | 2 | $2\times 10^3$ | 无 | 28 | 2s | | 3 | $2\times 10^4$ | $y = x + 1$ | 20 | 3s | | 4 | $3\times 10^4$ | 无 | 40 | 3.5s | 对于 $100\%$ 的数据,$2\leq n\leq 3\times 10^4$,$1\leq x,y\leq n$,$0\leq w\leq 10^9$。