题解：P12511 [集训队互测 2024] 树上简单求和

· · 题解

三种做法。

Part 1. 树分块

首先一条路径拆成四条根链。

对两棵树都随机撒点分块，使得每个点向上走 O(B) 步都能走到一个关键点。

  1. T1 关键点根链 -> T2 关键点根链。预处理出贡献系数即可。
  2. T1 关键点根链 -> T2 单点。对 T1 进行 dfn 序分块，变为 dfn 序上的 O(B) 单点加 O(1) 区间查问题。
  3. T1 单点 -> T2 关键点根链。对 T2 进行 dfn 序分块，变为 dfn 序上的 O(B) 区间加 O(1) 单点查问题。
  4. T1 单点 -> T2 单点。直接映射就行。

复杂度 O(n\sqrt n)。

一个有一点变化的做法：T1 不分块，维护 T1 每个根链到 T2 关键点根链的贡献系数，T1 根链-> T2 单点一样是 dfn 序分块。需要逐块处理才能做到线性空间复杂度，而且常数感觉很大。

Part 2. 树剖+分块

链通过树剖拆成 O(\log n) 个区间，然后就变成了一个经典问题：a 区间加，查 a_{p_{[l,r]}} 的和。

设左侧为 [1,n]，右侧为 p_{[1,n]}。 对两侧都分块，维护两个大小为 n/B 的 left,right 数组，求出 cnt_{i,j} 表示左侧前 i 个块对右侧第 j 个块的贡献系数。

  1. 整块 -> 整块：通过 cnt 的值，修改 right。
  2. 整块 -> 单点：先不贡献到右侧，使用 left 记录即可。
  3. 单点 -> 整块：修改 right。
  4. 单点 -> 单点：直接记录即可。

复杂度 O(n\log n\sqrt n)，非常快！

Part 3. 括号序/欧拉序分块

对两棵树求欧拉序，然后第一次出现贡献为 +1，第二次出现为 -1，那么，一条根链就相当于括号序中的一段前缀贡献的和。使用 Part 2 中的序列分块手法维护即可。复杂度 O(n\sqrt n)，不知道快不快。