01 trie

一、简介

01 trie 通过将数值的二进制建立 trie 树，可以解决维护异或极值、异或和等问题。

题意：

求树上两节点间边权异或值的最大值。

思路：

首先根据异或的性质，异或偶数次相当于没操作。因此我们钦定一个根 $root$ ，预处理出每个节点 $i$ 到 $root$ 的边权异或值 $sum_i$ ，然后问题就转化为：对于每一个 $sum_i$ ，求出它的异或最大值，而这就可以用 01 trie 来解决。

开始先对每个 $sum_i$ 都加入到 01 trie 中，这里就是普通的 trie 树操作（之前 AC 自动机里用到过）。然后怎么查询呢？我们用到贪心的思维，因为最高位为 $1$ 比后面所有为 $1$ 都要打，因此我们从高位到低位，尽量走不同的值。