c++ - 高效查询路径 u 到 v

Question

我一直在解决一个问题，但无法找到有效的解决方案。

问题陈述：

给定一棵具有 N 个顶点和 N-1 条边的树。每个顶点 v 表示由 C[v] 给出的值，其中 C[ ] 是一个数组。对于这棵树，我们必须执行 Q 查询，如下所示：

查询由两个整数 u,v 给出。让我们定义一个值 A，它由位于 u 和 v 之间的简单路径上的所有节点的值的乘积给出。

更正式地说，如果 u 和 v 之间的简单路径是 [u,a,b...,v]，那么

A = C[u] * C[a] * C[b] * ... * C[v]。

对于这个查询，我们需要输出 A 的除数数。

约束： 1<= N,Q <=100000, 1<= C[i] <=1000000 对于所有 1<= i <=N。

我的方法：由于产品可能非常大，我将主要因素及其计数存储为答案。

我首先使用二进制提升预先计算了树的 LCA。然后我为每个节点定义了一个 map< int, int >，它存储了从根到当前节点的主要除数及其乘积计数。这可以通过一个简单的 DFS 和一个用于合并地图的单独函数来实现

（注意：我正在使用O(LogN)中的筛子找到节点的素数分解）

然后对于 [u,v] 类型的每个查询，我都在寻找 LCA（比如说L）。现在我从 u 的映射中减去 L 的映射（注意：L 的映射将始终是 u 的映射的子集），对于节点 v 也是如此。

现在我有了产品的所有主要因素及其数量。

现在简单地使用结果，对于一个数字 K = a^p * b^q * c^r...，除数的数量 D = (p+1) * (q+1) * (r+1)。 ..我们得到答案。

时间复杂度分析：

让我们将 M 定义为最多 1000000 个不同的素数。

DFS 将在 O(N*M) 时间内运行：对于每个节点，在组合映射时，最坏的情况是出现所有 M 以内的素数。

LCA 预计算：O(NLogN) 时间

筛预计算：O(NLogLogN) 时间

每个查询将在 O(M+LogN) 时间内运行：O(LogN) 用于查找 LCA，O(M) 用于减去地图以找到产品的主要因素。

所以时间复杂度： O(NLogN + NM + NLogLogN + QMLogN)。

现在的问题是，在最坏的情况下，M 的数量级是 50000。所以这会增加时间复杂度。还有其他有效的方法吗？

答案必须以 1e9+7 为模报告

标签： c++algorithmgraphtree