B

给定一棵树。多次询问 $l_1,r_1,l_2,r_2$ 求

\[\operatorname{lca}([l_1,r_1],[l_2,r_2])=\bigoplus\limits_{u\in[l_1,r_1],v\in[l_2,r_2]}\operatorname{lca}(u,v) \]
$n,q\le5\times10^4$$

首先必须有一个在线 $O(1)$ LCA。显然可以转化到 DFS 序上 RMQ。

换根 LCA 的 trick：

\[\operatorname{lca}_{rt}(u,v)=\operatorname{lca}(rt,u)\operatorname{xor}\operatorname{lca}(rt,v)\operatorname{xor}\operatorname{lca}(u,v) \]

显然左边一定与右边三项中的一个相等。分讨可证，另外两个总会是相同的值抵消。则可以固定根，问题转变为求：

\[\operatorname{lca}(rt,[l_1,r_1])\operatorname{xor}\operatorname{lca}(rt,[l_2,r_2])\operatorname{xor}\operatorname{lca}([l_1,r_1],[l_2,r_2]) \]

只需知如何解决最后一项。显然这个东西套路差分容斥，就是求：

\[\operatorname{lca}([1,x],[1,y]) \]

注意到求一段到另一段的贡献，套路分块，变成若干整块到前缀的贡献，做前缀和变为整块前缀到任意前缀的贡献。这样可以做到 $O(nB)$ 时空预处理。散块的 $\operatorname{lca}([bl_x,x],[1,y])$ 则可以同样容斥为 $\operatorname{lca}([1,bl_y],[1,x])\operatorname{xor}\operatorname{lca}([1,bl_y],[1,bl_x))$。

只需处理散块到散块的贡献。这部分只好暴力变成 $O(B^2)$，这样很明显 $B=n^{1/3}$ 复杂度应该在 $O(n^{5/3})$ 级别，但实际上询问用前缀和不需要遍历整块，这部分单次 $O(B^2)$，而且很多层容斥常数巨大，所以 $B$ 应该适当调小。