#C241101C. 树
标签（Label）
- Trie树
- xor
网址（Website）
题目（Problem）
样例
输入数据 1
1
2
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
3
1 2 2
2 3 1输出数据 1
21
2【样例1解释】
对于第一组数据，当 $u_0, v_0, u_1, v_1$ 分别取 3,4,8,9 时取得最大值 $14+7=21$。
对于第二组数据，当 $u_0, v_0, u_1, v_1$ 分别取 1,2,3,3 时取得最大值 $2+0=2$。注意，如果取 $u_0=1, v_0=3$，则不存在任何一组合法的 $u_1, v_1$。
【样例2】
见选手目录下的 $tree/tree2.in$ 与 $tree/tree2.ans$。
【样例3】
见选手目录下的 $tree/tree3.in$ 与 $tree/tree3.ans$。
【样例4】
见选手目录下的 $tree/tree4.in$ 与 $tree/tree4.ans$。
【样例5】
见选手目录下的 $tree/tree5.in$ 与 $tree/tree5.ans$。
【样例6】
见选手目录下的 $tree/tree6.in$ 与 $tree/tree6.ans$。
【样例7】
见选手目录下的 $tree/tree7.in$ 与 $tree/tree7.ans$。
题解（Solution）
$\qquad$可以用 $01\text{Trie}$ 树解决到根的最大路径异或和 $ans1$ ，然后找到最大的异或链。对于不在链上的点，把这些点的子树都建出 $01\text{Trie}$ 求出最大路径异或和 $ans2$ ，把最终的答案与 $ans1+ans2$ 取 $\max$ ；把链断开，分别求出左右子树的最大路径异或和，记得实时维护 $\text{Trie}$ 树，保证时间复杂度。
$\qquad$时间复杂度 $O(n\log v)$ 。
出题者题解
算法分析
考虑要求两条链不相交，那其实就是选一条边断开，对于两棵树分别求解最大值，然后要求和最大。
考虑如果只要求求出全局最大的链，那应该如何求呢，其实只需要求出每个点到根的异或和，然后就变成了全局最大异或点对，这个直接用 01 trie 就可以做到 $O(n \log v)$ 的复杂度求出答案。
那就先求出全局最大的链，考虑以链的一个端点为根。
先考虑我们不断链上的边的情况，这种情况下我们可以发现，由于子树外的贡献是一定的，恒为全局最大的链，那么就只需要子树内的最大异或点对最大就可以了，然后这个可以直接对每个被链分裂出的子树求一遍答案就可以了，因为包含的点数越多，答案是越大的。
然后考虑断链上的边的情况，这就相当于链上的问题，可以处理前缀答案和后缀答案，因为总的增量是 $O(n)$ 的，所以还是可以在 $O(n \log v)$ 的复杂度内求出前缀答案和后缀答案，然后枚举边拼接就可以了。
总时间复杂度 $O(n \log v)$。
代码（Code）
