异或最大值,考虑线性基;树上路径问题,考虑点分治
于是不难得到,在某一次分治的时候,处理lca为当前根的所有询问。具体地,求出每个点到当前根的线性基,然后对于一对点,暴力合并两个线性基(也就是两个向量组的并集的极大无关组等于两个向量组的极大无关组的并集的极大无关组)即可
这道题目显然使用贪心构造线性基更easy(关于贪心构造线性基,在insert
函数中判断插入的数是否为\(0\),如果为\(0\)直接返回可以极大提升代码效率,一个卡常trick)
注意时间复杂度,考虑处理每个询问的时候,每一层的时间复杂度是\(O(q)\)的,相当于会把每个询问走一遍,别认为每个询问会走很多次然后就认为TLE了
还有注意特判\(x=y\)的情况。树这题不用特判\(x=y\)是因为这种不符合题意
洛谷题解还有在线的做法,可以学一下
标签:数字,极大,询问,特判,线性,幸运,复杂度,每个 From: https://www.cnblogs.com/dingxingdi/p/18170676