【题解】CodeForces 1902F Trees and XOR Queries Again-526互联

传送门：https://codeforces.com/contest/1902/problem/F

数据结构题，这里讲两种思路。

$ST$ 表思路：

判定“从若干个数中能否取出其中一些，使得异或和为 $x$”的问题，第一时间想到线性基，本题要做的显然就是快速求出询问路径上所有数的线性基。两组数的线性基可以合并，方法为“暴力将一组线性基中的所有数插入另一组线性基”，单次合并时间复杂度为 $O(log^2 V)$；我们使用 $ST$ 表，在 $ST_{x,i}$ 中存储从点 $x$ 到 $x$ 的第 $2^i-1$ 辈祖先路径上所有数的线性基；每次询问时的合并与序列上的 $ST$ 表相仿，设询问两点为 $x、y$，在树上 $lca$ 为 $z$，则将 $x$ 到 $z$、$y$ 到 $z$ 的路径各用 $ST$ 表中两个元素表示即可。

构建 $ST$ 表的复杂度为 $O(n$ $logn$ $log^2V)$，查询复杂度总共为 $O(q$ $log^2V)$，注意细节即可通过；

（本方法的一个卡常技巧：合并两组线性基的时候，如果有一组线性基每一位上都有数，直接把那一组传回去就行了；另外，把有意义位数少的线性基插入到有意义位数多的里面，也可以卡一点常？）

点分治思路：

虽然 $O(n$ $logn$ $log^2V)$ 在经过上述卡常后已经可以稳定通过本题，但这里介绍一种 $O(n$ $log^2V)$ 的做法——点分治。

思路出乎意料地简单：对给出的树进行点分治，在重心 $x$ 上统计所有在以 $x$ 为重心的子树内且穿过 $x$ 的询问路径的线性基；对于整棵以 $x$ 为重心的子树，我们统计每一个点到 $x$ 的路径上数的线性基，这可以在 $O(n$ $logn$ $logV)$ 的时间内解决（以 $x$ 为根遍历整棵子树，每次将一个点上的值暴力插入其父亲到 $x$ 的线性基，即为其自身到 $x$ 的线性基）；而每当处理穿过 $x$ 的询问，我们就暴力合并 $x$ 两边的两条路径的线性基，得到询问路径的线性基；这样的操作只需要进行 $q$ 次，因此复杂度为 $O(q$ $log^2V)$；

总复杂度即为 $O(q$ $log^2V)$（$n、q$ 同级）。

一点小发现：

对于链上信息的合并，树链剖分、$ST$ 表、点分治三种常见方法的对比如下：（注：这里默认树链剖分后使用线段树/$BIT$ 存储信息，因为如果可以使用 $ST$ 表，则这种情况下的树剖是没有必要的，显然不如直接 $ST$ 表更优；）

树链剖分：

1. 可支持在线/离线/修改；

2. 构建复杂度为 $O(两区间信息合并复杂度*n)$；

3. 单次查询复杂度为 $O(两区间信息合并复杂度*log n*logn)$；

ST表：

1. 可支持在线/离线，不支持修改，只能查询满足“两区间的信息合并结果=两区间的交的信息合并结果”（即统计重叠不影响结果）的信息，例如线性基、最值；

2. 构建复杂度为 $O(两区间信息合并复杂度*n$ $logn)$；

3. 单次查询复杂度为 $O(两区间信息合并复杂度)$;

点分治：