题目描述
给定一棵 n 个点的无根树,边有边权。
令 V(x,y),E(x,y) 分别表示树上 x,y 之间的简单路径上的所有点的集合和所有边的集合,特别地,当 x=y 时,V(x,y)={x},E(x,y)=∅。
再令边集 E 的权值 f(E) 为 E 中所有边的权值的 异或和,当 E=∅ 时,f(E)=0。
现在,要你求出
1≤x,y,u,v≤n,V(x,y)∩V(u,v)=∅max(f(E(x,y))+f(E(u,v)))通俗的讲,你要选择两条简单路径,满足没有重合的点,且边权异或和之和最大。
输入格式
第一行一个整数 n,表示树上点的个数。
接下来 n−1 行,每行三个整数 x,y,w,表示编号为 x 和 y 的点之间有一条权值为 w 的边。
输出格式
一行一个整数,表示答案。
提示
【样例 1 解释】
样例中的树如图所示,选择标红色和蓝色的两条路径,满足没有重合的点,且边权异或和之和最大,为 (7⊕1⊕8)+(5⊕2)=21(其中 ⊕ 表示异或运算)。

【样例 2 解释】
样例中的树如图所示,为一条链的形状,选择标红色和蓝色的两条路径,蓝色路径退化成了一个点,使异或和之和达到最大值 2+0=2。注意红色路径并不能延申到 3,否则蓝色路径将无法存在。

【数据范围】
本题采用捆绑测试。
子任务编号 |
n≤ |
特殊性质 |
分值 |
时限 |
1 |
50 |
无 |
12 |
1s |
2 |
2×103 |
28 |
2s |
3 |
2×104 |
y=x+1 |
20 |
3s |
4 |
3×104 |
无 |
40 |
3.5s |
对于 100% 的数据,2≤n≤3×104,1≤x,y≤n,0≤w≤109。