题目分析

我们有一棵 $N$ 个节点的树，每个节点有一个初始高度 $H_j$（$0 \le H_j < L$）。支持两种操作：

1. 洒水操作：以节点 $X$ 为中心，半径 $D$ 内的所有节点高度乘以 $W$ 后对 $L$ 取模
2. 查询操作：询问某个节点的当前高度

关键限制：$D \le 40$，这个限制是解题的突破口。

核心思路

1. 问题转化

直接遍历每个操作影响的所有节点是不可行的（$N,Q$ 太大）。由于 $D$ 很小，我们可以考虑标记传递的方法。

核心思想：将一次洒水操作的影响记录在相关节点上，查询时再收集所有影响。

2. 标记设计

对于每个节点 $u$，我们维护一个数组 $mul[u][d]$（$0 \le d \le 2D_{\max}$），表示"对距离节点 $u$ 为 $d$ 的所有节点施加的乘法因子的累积乘积"。

为什么数组大小是 $2D_{\max}$？

• 因为一个洒水操作 $(X, D, W)$ 可能影响 $X$ 的祖先节点，对于祖先节点 $v$，它到 $X$ 的距离为 $h$，那么它需要记录对距离自己为 $D-h$ 的节点的影响。
• 最坏情况下 $h = D$，此时 $D-h = 0$；$h = 0$ 时 $D-h = D$；同时还要考虑另一个方向的影响。

3. 洒水操作的处理

对于洒水操作 $(X, D, W)$：

1. 从 $X$ 开始向上遍历祖先（包括 $X$ 自己），设当前节点为 $v$，$v$ 到 $X$ 的距离为 $h$
2. 如果 $h > D$，停止向上遍历
3. 剩余半径 $r = D - h$
4. 将 $mul[v][r]$ 乘以 $W$（模 $L$）

这样，我们就把洒水操作的影响记录在了 $X$ 及其祖先节点上。

4. 查询操作的处理

要查询节点 $u$ 的当前高度：

1. 从 $u$ 开始向上遍历祖先（包括 $u$ 自己），设当前节点为 $v$，$v$ 到 $u$ 的距离为 $h$
2. 如果 $h > D_{\max}$，停止向上遍历
3. 用 $mul[v][h]$ 乘到结果上（模 $L$）

为什么这样是正确的？

• 对于任意洒水操作 $(X, D, W)$，如果它影响了节点 $u$，那么 $u$ 到 $X$ 的距离 $dist(u,X) \le D$
• 在洒水时，我们在 $X$ 的某个祖先 $v$ 处记录了影响，且 $dist(v,X) + dist(v,u) = dist(X,u) \le D$
• 查询时，$u$ 会访问到 $v$，且 $dist(v,u)$ 正好对应洒水时记录的位置

5. 时间复杂度分析

• 每次洒水操作：向上遍历至多 $D$ 个节点，$O(D)$
• 每次查询操作：向上遍历至多 $D$ 个节点，$O(D)$
• 总时间复杂度：$O((N+Q)D)$，在 $D \le 40$ 时非常高效

算法优势

1. 利用了小半径特性：$D \le 40$ 使得我们可以为每个节点存储大小为 $O(D)$ 的数组
2. 标记永久化：不需要下推标记，简化了实现
3. 树上差分思想：将区间修改转化为多个点的标记更新
4. 离线处理：算法本质是在线算法，但思想类似于离线差分

总结

这道题的解决关键在于：

• 发现 $D$ 很小的特殊性质
• 设计合适的标记结构 $mul[u][d]$
• 利用树的父子关系实现高效的标记更新和收集
• 通过"洒水时分散标记，查询时收集标记"的方式避免直接遍历影响区域

这种"小半径操作 + 标记永久化"的思路在树上操作问题中非常有用，特别是当操作半径有上限时。