题解 P8214 [THUPC2022 初赛] 赫露艾斯塔 / P8204 [Ynoi2005] tdnmo

· · 题解

每次讲都是脑子会了嘴巴没会，但万幸的是手还会写题解/hanx

场上题都不知道是什么但万幸没开，毕竟我树分块早就忘完了更别说想到了（

不过想到树分块貌似就简单了？

有向邻域的不删除莫队。

先以一般的角度考虑这个问题：这是一道构造题！人畜无害，一点也不数据结构！

观察 2.5\times 10 ^ 9，大概是 n \sqrt m + m\sqrt n 的数量级，分块吧。

这里默认大家都会 top cluster 树分块，不会的可以参考 我的博客（不过现在个人觉得讲的不是很好），gxy001 的博客，以及青蛙的集训队论文《浅谈一类树分块的构建算法及其应用》，这里不重点展开。

不过您也可以选择先看完这篇题解之后再去学习 top cluster 树分块，我会把需要的东西都大致讲一下，划分方法可以看完再去学。

简要地讲解一下：top cluster 定义簇为树上的连通块。树分块将一棵树分成了许多个簇，这些簇只有二度簇（可以理解成簇内只有两个端点与其他簇联通），一度簇（簇内只有一个端点与其他簇联通）。

而很显然，簇之间的交只有可能是各自的端点。

并且若设置一个阈值 B，该种分法将所有簇的大小控制在 B 以内，将簇的个数控制在 \frac{6n}{B} 之内。

这里给出对样例的树的划分来辅助理解：

其中不同的颜色代表不同的簇。

考虑在进行划分之后，我们对所有的询问 N(x_i,y_i) 进行分类：

考虑对于 1 类询问，我们对于每个二度簇进行处理。可以先处理出每个节点在根为 1 时的深度，记第 i 个簇深度较深的端点为 btm_i，将挂在 btm_i 的所有询问 N(x_j,y_j) 拿出来，按照 dep_{x_j} + y_j - dep_{btm_i} 的大小进行排序。

这里再来一张图，就不信看不懂了。

假设排序后询问 x 排在 y 前面：

其中棕色的部分表示两个询问的有向邻域包含的点中，在簇内的部分；未涂色的部分表示不在簇内的部分。

考虑这么构造操作：若当前处理排序后第 u 个询问，记 V_u = dep_{x_u} + y_u - dep_{btm_i}，则跳到 N(btm_i,V_u)；然后跳到 N(x_u,y_u) 声明后撤回此次跳跃，再跳到下一个 N(btm_i,V_{u + 1}) 去处理第 u + 1 个询问；处理完当前簇的所有询问时回到 N(1,0)。

我们发现，这样的跳跃在按照 V_u 排序后总是合法的；考虑每次跳跃的代价就是相邻两个有向邻域点量的差异，对于从 N(btm_i,V_u) 跳到 N(x_u,y_u)，增加的只会是树簇内的点，即对于每个询问摊一个 B 的代价，若 1 类操作一共有 m_1 个，则此处的贡献代价是 O(m_1B)。

对于从 N(btm_i,V_u) 跳到下一个 N(btm_i,V_{u + 1})，每次只会向 btm_i 的子树内扩展，对于每个簇的贡献代价不超过 n，则此处的贡献代价是 O(\frac{6n ^ 2}{B})。

综上，我们证明了对于 1 类询问的总贡献代价不超过 O(\frac{6n ^ 2}{B} + m_1B)，操作次数为 5m_1。

对于第二类询问，其 x 有可能处于一个一度簇内，有可能处于二度簇的非路径节点上，不过不管 y 怎么变，其有向邻域所能囊括的点都在 x 所在的簇内，其大小不超过 B，所以直接跳过去声明后跳回 N(1,0) 就行了，设一共有 m_2 种二类操作，这里的贡献代价不超过 O(m_2B)。

综上我们得到了一种贡献代价不超过 O(\frac{6n^2}{B} + mB)，操作次数为 O(5m_1 + 3m_2) \leq O(5m) 的方法。细心的读者可能发现对于贡献代价中 \frac{6n ^ 2}{B} 也不是一个完全严格的上界，，因为当 B 一大了块也分不到这么多块，实际操作下来根本卡不到这么多，至于开 2.5 \times 10 ^ 9 不知道是不是就是这种做法的实际严格上界，不过我太菜了还不会完全证明。

最后提一下关于此题的树分块方法。由于我们只用知道每个簇的端点，所以只用记录每个节点下方是否有簇端点，子树内未被划入簇的点数量，当前节点所属簇的 btm_i 即可正确划分。