P6072 『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))) $$ 通俗的讲，你要选择两条简单路径，满足没有重合的点，且边权异或和之和最大。

无

无

【样例 1 解释】 样例中的树如图所示，选择标红色和蓝色的两条路径，满足没有重合的点，且边权异或和之和最大，为 $(7\oplus 1\oplus 8)+(5\oplus 2)=21$（其中 $\oplus$ 表示异或运算）。  【样例 2 解释】 样例中的树如图所示，为一条链的形状，选择标红色和蓝色的两条路径，蓝色路径退化成了一个点，使异或和之和达到最大值 $2+0=2$。注意红色路径并不能延申到 $3$，否则蓝色路径将无法存在。  --- 【数据范围】 **本题采用捆绑测试。** | 子任务编号 | $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$。