part 4

这场感觉就T4比较有意义

• LCA 结论：三个点两两求 LCA，lca 的编号异或起来是答案（到三个点的距离总和最小的点），且该答案是以其中一点为根时另外两点的 LCA。
• 所以我们可以得到结论 点 \(p\) 和点 \(q\) 以 \(x\) 为根的 lca 深度是 \(dlca_{p,q} \oplus dlca_{p,x} \oplus dlca_{q,x}\) 其中 \(dlca\) 表示两个点以 1 为根的 lca 深度
• 接下来我们考虑刻画 以 \(x\) 为根时 \(y\) 子树内的所有点
  • \(x = y\) 则为全树(以 1 为根的子树)
  • \(x \neq y\) 且 \(x\) 不在 \(y\) 的子树内，则为以 \(y\) 为根的子树
  • \(x \neq y\) 且 \(x\) 在 \(y\) 的子树内，则为全树扣掉 \(y\) 的某个儿子（\(x\) 的祖先）的子树
• 所以我们现在只需要解决以 \(y\) 为根的子树的每个点和 \(z\) 或者 以 \(z\) 为根的子树的每个点在以 \(x\) 为根的情况下的 \(lca\) 的深度的异或和即可
• 再根据上面推出来的结论所以 \(x\) 的换根对于我们来说已经没有了影响
  • 因为我们可以分别求出异或和再把它们异或起来
• 我们定义 \(x \oplus y\) 表示 \(x\) 连续异或 \(y\) 次。
• 我们先来考虑以 \(y\) 为根的子树的每个点和 \(z\) 在以 1 为根的情况下的 \(lca\) 深度的异或和
  • 若 \(z\) 不在 \(y\) 子树内或恰好等于 \(y\) 那么答案就是 \(dlca_{y,z} \oplus siz_y\)
  • 否则假设 \(z = a_0 -> a_1 -> a_2 -> …… -> a_{k-1} -> a_k = y\) 那么答案就是 \((d_z \oplus siz_z) \oplus \oplus_{i=1}^{k}(d_{a_i} \oplus (siz_{a_i} - siz_{a_{i-1}}))\) 其实就是 \((d_y \oplus siz_y) \oplus \oplus_{i=0}^{k-1}((d_{a_i} \oplus d_{a_{i+1}} \oplus siz_{a_i}))\) 后面这个很显然是一个前缀和的形式故可以预处理快速计算
• 接着我们考虑以 \(y\) 为根的子树的每个点和 以 \(z\) 为根的子树的每个点在以 1 为根的情况下的 \(lca\) 的异或和
  • 若它们互不相交则为 \(dlca_{y,z} \oplus (siz_y \cdot siz_z)\)
  • 不妨设 \(z\) 在 \(y\) 的子树内，若在 \(y\) 子树内选的点不在 \(z\) 子树内则和上面的情况完全相同，否则我们发现在 \(z\) 子树内选两个点求 \(lca\) 深度，只有选的两个点相同时才不会被抵消到因为如果存在 \((u,v)\) 的话一定会存在 \((v,u)\) 所以我们可以预处理出每个子树内所有点的深度的异或和即可