CF1055F Tree and XOR

题意：给出一棵 个点的树，边有边权。

求 个点对中第 小的路径异或和。

，，时限 。

---

首先，任取某点为根，求出每个点的前缀异或和。

由异或的自反性，路径异或值就是两端点前缀异或和的异或。

现在就变成了一个集合问题：求第 小异或 。

---

考虑按位贪心。

首先看看第一位为 的方案数，答案是第一位为 的数的个数的平方和。

若 比这个数大，则第一位可以为 ，否则为 。

然后，第一位就被限定了。

总的来说，我们要支持：查询 中，前若干位为 的方案数。

可以先枚举其中一个，就能得知另一个的前若干位。

可以先建立 ，每个数都记录其对应的另一个数的范围，不难发现必然是 的一颗子树。

每确定一位，各个数的范围就会向下走一步。

这样空间是 的，并不能通过。

将 滚动一下（按位分治）就可以做到 空间。