算是个笔记吧。

一棵 $n$ 个点的树，带边权，每次给定 $u,v$ 求从 $u$ 到 $v$ 的路径上的边权乘积，带模数，强制在线。

然后把询问搞得多一点，这个时候就要求我们的查询得要在常数时间内完成。

这里给出一种预处理 $O(n\log n)$（空间同）单次查询 $O(1)$ 的常数巨大的做法。

首先把询问拆成两个点分别到 LCA，这一步显然可以用欧拉序+ST表等方式在这个时空限制内完成。

把树剖一下。然后发现一个点到祖先的路径可以拆成一条“一个点到一个链顶”的路径，和最后一小段一个点到祖先的路径，分别做即可。

对于最后那段查询，它的两个端点在一条重链上，所以在 dfn 序上连续，问题转化为在序列上询问，猫树做掉。

然后之前那些“一个点到一个链顶”的询问，观察到一个点到根至多有 $O(\log n)$ 个链顶，那么可以把所有这样的路径预处理出来然后做掉。

至于如何预处理，可以每个点后面拖个列表表示这个点到根路径上的链顶们的答案。每个点直接从父亲继承这个列表然后每个更新一下，如果自己是链顶那么在列表后面加个数挂着就好了。时空复杂度 $O(n\log n)$。

那么还剩两个事：

• 给定一个点和一个链顶，找到这个点的列表中这个链顶的出现位置。

对于每种这样的一个点和一个链顶，把答案存下来就好了。因为列表里有这个链顶的点一定都在这个链顶的子树内，dfn 序连续，所以很好算，每个链顶后面拖个位置列表就好了。

• 之前提到的一个点到祖先的询问中，那个“分界”链顶（也就是前面用上述预处理，后面用猫树）是哪个。

找到祖先点所在链的链顶，按照上述找出现位置的方法找到在那个点的列表中出现在了哪里，进行一个 1 的偏差即可得到分界链顶的位置，进而将其求出（不过其实就不用求出来了，直接查前缀和就好了）。

于是我们的问题就解决了。

板子题还没找到，代码没写过，目测常数巨大。不过如果 $n$ 稍微小一点，似乎是可以接受的（因为常数主要在预处理）。

以上。