对 @LHF dalao 的题解进行一些补充说明。因为他讲的实在是太难懂了。最后在 @_•́へ•́╬_ dalao 的帮助下才勉强知道怎么做。不过他的代码非常简洁易懂，有需求的可以去看他的代码。我就不放了。
本文章分析复杂度时认为 \(n\) 与 \(m\) 同阶。
首先需要明确的是，\(a\) 子树中所有与 \(a\) 的距离模 \(x\) 等于 \(y\) 的节点就是 \(a\) 子树中深度模 \(x\) 等于 \((dep_a+y)\bmod x\)（下文设其为 \(k\)）的节点。这样我们就可以把修改转化为将一个点的子树内所有深度模 \(x\) 为 \(k\) 的节点权值加上 \(z\)。
显然这种数据结构题不可能一个点一个点地去修改。因此先求出 dfn 序。这样就可以把修改变为对 \([dfn_a,dfn_a+size_a-1]\) 范围内（下文设其为 \([l,r]\)）的点进行一次区间操作。
但是我们不可能将 \([l,r]\) 范围内的所有值统一加上某数。因此考虑建立一个以 dfn 序为 \(x\) 轴，深度为 \(y\) 轴的平面直角坐标系。把第 \(i\) 个点放在坐标 \((dfn_i,dep_i)\) 上。这样我们就把修改转化为将所有横坐标在 \([l,r]\) 范围内，纵坐标模 \(x=k\) 的节点权值全部加上 \(z\)。
考虑直接暴力跳纵坐标，将跳到的水平线的 \([l,r]\) 部分全部加上 \(z\)。因为 dfn 序与深度不对应的坐标是空着的，没有放点。所以把 \([l,r]\) 的整个部分全部加上 \(z\) 不会影响正确性。
用某种数据结构维护每个纵坐标对应的水平线。当 \(x > \sqrt n\) 时，暴跳的复杂度就是 \(O(\sqrt n) \times O(Modify)\) 的。查询时直接单点查询，因此复杂度是 \(O(1) \times O(Query)\) 的。其中 \(O(Modify)\) 表示这种数据结构修改的复杂度，\(O(Query)\) 表示它查询的复杂度。因此使用修改 \(O(1)\)，查询 \(O(\sqrt n)\) 的序列分块+差分即可达到最优总复杂度。
当 \(x \leq \sqrt n\) 时，暴跳的时间复杂度可能会直接退化到 \(O(n)\)。因此考虑根号分治，将这部分特殊处理。开一个 \(\sqrt n \times \sqrt n\) 的某种数据结构的数组，记为 \(DS_{i,j}\)。每次修改对 \(DS_{x,k}\) 执行一次让 \([l,r]\) 区间加 \(z\) 的操作。询问时给答案加上 \(\sum\limits_{i=1}^{\sqrt n} DS(i,dep_a \bmod i,dfn_a)\) 即可。修改复杂度为 \(O(1) \times O(Modify)\)，询问复杂度为 \(O(\sqrt n) \times O(Query)\)。因此使用修改 \(O(\sqrt n)\)，查询 \(O(1)\) 的序列分块即可达到最优总复杂度。
因为这两种处理都用到分块，所以可以直接把散块暴力算，整块再分类讨论。
时空复杂度 \(O(n \sqrt n)\)。时间限制十分充裕，但空间限制不够。可以通过调块长和根号分治的阈值卡过去。
代码就不放了，有需求的可以去看 @LHF dalao 的题解中的代码。
标签：stdmxeypz,题解,复杂度,sqrt,times,P7710,修改,dfn From： https://www.cnblogs.com/DRPLANT/p/P7710_stdmxeypz_solution.html