题解：P8498 [NOI2022] 树上邻域数点

· · 题解

树上邻域数点 树分块长剖题解。

设常数 b，考虑将邻域分为 [b^i,b^{i+1}) 的一些块。对于所有的 [b^i,b^{i+1})，我们将整棵树按照 b^i 分块来处理所有大小在这个区间中的邻域。

我们发现，这个区间中的所有邻域大小都 \geq b^i，所以一定完全覆盖了邻域中心所在的块。所以我们把这一整个块和上界点的一个外邻域和下界点的一个内邻域 Compress 起来即可。

为了求这两个东西，我们考虑先求出每个块中上界点和下界点在簇内的所有大小的邻域，然后再在收缩树上换根 dp 求出上述两个东西。

为了求前者，我们考虑长剖。对于每个节点我们维护两个序列：一个差分 tag 序列和一个真实值序列（称为 A 和 B）。对于 dp 序列中的一个位置 i，其真实值为 C(B_i,C(A_0,C(A_1,C(A_2,C(\dots A_i)))))。考虑合并长儿子和一个短儿子：设短儿子高度为 h，对于前 h 项，我们求出两个儿子分别的真实值然后 Rake 起来。对于后面的部分，我们把长儿子的 A 序列前 h+1 项 Compress 起来，然后再 Rake 上短儿子整体的真实值。

这样我们就几乎做完了。但是这个做法有两个问题。第一个是，我们希望我们得到的簇的两个界点正好是当前块的两个界点（要不然没法跟簇外面的东西合并）。我们把一个界点作为根的时候，实际上的另一个界点是其所在长链链底。所以，我们强制把簇路径设为根节点所在长链；这部分合并的时候要先补齐到真实长链的高度。同时，对于当前块的另一个界点子树内，我们将这部分信息整体 Rake 到其和其父亲的边上。这样就能保证另一个界点就在这个点上了。

第二个问题是，我们在处理第 h+1 项时，如果本来长儿子前 h+1 项都是 empty，那处理过后这一个位置的 A 值的另一个界点就会变成短儿子子树内的点。所以我们把 tag 分为两种，Compress Tag 和 Rake Tag。如果发生了这种情况，我们就在这个位置上打一个短儿子的 Rake Tag。在获取真实值，也就是把 Tag “往前推”的过程中，如果遇到一个 Rake Tag，就把他和当前的真实值 Rake 起来并且复制到下一个位置。如果下一个位置已经有 Compress Tag，那么直接把这两个 Tag Rake 起来即可。

长剖部分就到此结束了。然后我们在收缩树上换根 dp，将每个簇内部的邻域和收缩树上这个方向上所有儿子的 dp 值 Rake 后 Compress 起来即可。这样每次查询的时候需要 Compress 两次，所以我们把内邻域的 dp 值提前和整个块合并一下，就只需要一次了。

此时取 b\in[3,3.2] 是比较优的，可以获得 90 分，无法通过最后两个测试点。不过我们发现，所有的内邻域不需要经过值域分块后长剖，而可以先记录下来然后在一开始用一个整棵树的大长剖 dp 求出来。这样可以削掉很多合并次数。同时注意在实现的时候不要重复进行很多本质相同的合并（例如目前需要合并的深度已经超过了子树深度）。此时的总操作次数大概在两千八百万，可以通过。

https://qoj.ac/submission/2096188