题解：P5399 [Ynoi2018] 駄作

· · 题解

参考资料：周欣《浅谈一类树分块的构建算法及其应用》。

花了一天多的时间才过了这个题，写篇题解纪念一下。

前置知识: Top cluster 树分块

熟知 Top cluster 树分块的可以跳过这一个部分。

我们希望将一整棵树划分成若干个树簇，树簇是树上的一个连通块，并且一个簇内最多只有两个点与外界相连，我们称这两个点为界点。在实际运用中，我们要求其中一个界点是这个簇中深度最浅的点，称为上界点；剩下一个节点称为下界点。特别注意：一个界点可以属于若干个簇，但它最多是一个簇的下界点。

我们先考虑什么时候一个点 u 可以是界点，在深搜过程中，u 是界点当且仅当满足下面三个条件中的至少一个：

  3. 删去 u 子树中的界点以及界点的子树后，剩下点的数量超过了 B。

通过如上的构造方式，我们可以使得界点的数量不超过 \frac{2n}{B}，理由如下：第三种情况最多只会出现不超过 \frac{n}{B} 次，第二种情况的 u 的至少有两棵子树含有因为第三种情况而产生的界点，因此第二种情况发生数量一定小于第三种情况，因此总共界点数量不超过 \frac{2n}{B}。

我们再考虑如何划分簇，我们考虑以任意顺序遍历 u 的子树并维护一个集合 S 存储应该放到一个簇中去的所有未划分点。我们考虑什么时候应该清空 S，并将子树中的未划分点分到新的簇中去：

  1. 加入新子树的未划分点后，S 的大小将会大于 B。
  2. 加入新子树的未划分点后，S 将会有多于 1 个下界点，违背了条件。
  3. 在先前我们没有处理 u 的任意子树。

我们可以发现，这样划分的每一个簇的大小都不会超过 B，而且簇的数量不会超过 \frac{6n}{B}（应该到不了这个上界），证明如下：第一类情况将当前子树和它的邻居进行配对，每一个组合的大小超过了 \frac{n}{B}，因此块数不超过 \frac{2n}{B}，第二类情况相当于“消耗”了一个下界点，第三类情况“消耗”了一个上界点，因此总共不会超过 \frac{6n}{B} 个块。

上述内容大部分来源于论文，但是我们应该注意到这样的划分方式有以下性质:

  1. 一个簇中最多有两个界点，一个簇外的点到达簇内的点必须经过这两个点的其中一个。
  2. 一个簇的上界点是这个簇中深度最小的点，这极大地简化了某些计算问题。
  3. 由于（2）的特性，我们可以建立一棵收缩树，将每一个簇的上界点和下界点连边，这一棵树的大小是 O(\frac{n}{B}) 的，很适合我们进行计算。

Solution

我们可以将题目中一个点的邻域拆分成每一个簇的邻域，并且由于 Top Cluster 的特殊性质，大部分的簇的邻域中心都是界点，只有 O(1) 个不满足条件。

因此，我们可以将贡献分成簇间贡献和簇内贡献分别处理,考虑计算所有的贡献:

  1. 不同簇之间的贡献。由于两个簇中的点之间的路径经过固定的点，我们可以在收缩树上进行树形DP来统计贡献，考虑当前点是 u：

    1. 点 x 和点 y 的贡献：我们可以预处理出点 x 到 x 所属簇下界点的距离 dl_x，因此 x 到 y 的距离可以写成 dl_x + dep_y - dep_u。
    2. 点 y 和点 z 的贡献：可以写成 dep_y + dep_z - 2dep_u。

    因此，我们可以处理对于每一个块，两个点对应的邻域的大小，深度和，到下界点的距离和就可以转移了，这里总共的时间复杂度是 O(m (B + \frac{n}{B}))。

  2. 一个簇内两个邻域之间的贡献，并且两个邻域的中心都是界点，考虑对于每一个块预处理所有的答案，f_{0/1,0/1,i,j} 表示第一个邻域是以上/下界点为中心，半径为 i，第二个邻域是以上/下界点为中心，半径为 j，暴力统计即可，每一块的时间复杂度是 O(B^2)，需要做二维前缀和，这里的时间复杂度为 O(\frac{n}{B}(B^2 + m))

  3. 一个簇内两个邻域之间的贡献，两个邻域的中心至少一个不是界点，对于对于每一个询问只会有 O(1) 个块会这样，因此 O(B) 地计算，考虑拆贡献 dist(a,b) = dep_a + dep_b - 2 dep_{LCA(a,b)}，前两项统计是容易的，后一项可以对于第一个邻域每个点到根（这里是上界点）的路径 +1，查询第二个每一个点到上界点的路径和，可以较为轻松的做到 O(B) 处理。这里的时间复杂度是 O(mB)。

不妨设 m 和 n 同阶，取 B = \sqrt{n}，时间复杂度可以做到 O(n\sqrt{n})。

Optimization

  1. 块长取 B = 2\sqrt{n} 比较优秀。
  2. 合理调整多维数组的顺序。
  3. 这里需要 O(1) 求 dist(a,b)，这个东西很慢，我们可以考虑预处理出每一个簇内的点到上下界点的距离，减少调用 dist(a,b) 的次数。
  4. 避免使用 DFS，改成循环效率更高。
  5. 尝试找到一种顺序，使其是原树的dfs序，并且每一个簇的访问是连续的，这可以考虑在做 Top Cluster 的时候“以任意顺序遍历子树”改成先遍历没有界点的子树，后遍历有界点的子树，这样就可以了，可以看图理解一下。

Code

代码常数较大，极限卡过仅供参考 查看代码。