1

给定一棵带有n节点的树（n可以大到2 * 10^5），其中每个节点都有一个与之相关的成本，让我们定义以下函数：

  • g(u, v) = the sum of all costs on the simple path from u to v
  • f(n) = the (n + 1)th Fibonacci number (n + 1 is not a typo)

我正在处理的问题需要我计算f(g(u, v))树中所有可能的节点对的总和 modulo 10^9 + 7。

例如，让我们以一棵带有3节点的树为例。

  • 不失一般性，假设节点1是根，它的子节点是2和3
  • costs[1] = 2, cost[2] = 1, cost[3] = 1

g(1, 1) = 2; f(2) = 2

g(2, 2) = 1; f(1) = 1

g(3, 3) = 1; f(1) = 1

g(1, 2) = 3; f(3) = 3

g(2, 1) = 3; f(3) = 3

g(1, 3) = 3; f(3) = 3

g(3, 1) = 3; f(3) = 3

g(2, 3) = 4; f(4) = 5

g(3, 2) = 4; f(4) = 5

10^9 + 7将所有值相加，并将结果取模26作为正确答案。

我的尝试：

我实现了一种算法，通过使用稀疏表找到最低的共同祖先来g(u, v) 计算O(log n)。

为了找到合适的斐波那契值，我尝试了两种方法，即在矩阵形式上使用幂运算，另一种方法是注意到序列modulo 10^9 + 7是循环的。

现在是极其棘手的部分。无论我如何进行上述计算，O(n^2)在计算所有可能的总和时，我最终还是会达到对f(g(u, v))。我的意思是，只进行n * (n - 1) / 2配对有明显的改进，但这仍然是二次的。

我错过了什么？我已经研究了几个小时，但是如果不实际产生二次算法，我看不到获得该总和的方法。

4

2 回答 2

2

要知道节点 X 的成本要包含在总和中的多少倍，我们将其他节点分为 3 个（或更多）组：

  • 连接到 X 左侧的子树 A
  • 连接到 X 右侧的子树 B
  • （子树 C、D ......如果树不是二叉树）
  • 所有其他节点 Y，通过 X 的父节点连接

当两个节点属于不同的组时，它们的简单路径经过 X。所以经过 X 的简单路径的数量为：

#Y + #A × (N - #A) + #B × (N - #B)

所以通过计算节点的总数N，以及X下的子树的大小，可以计算出节点X的成本应该包含在总和中的多少倍。对每个节点都这样做，你就有了总成本。

用于此的代码可能很简单。我假设节点总数 N 是已知的，并且您可以向节点添加属性（这两个假设都简化了算法，但没有它们也可以完成）。

我们将添加一个child_count来存储节点的后代数量，并添加一个path_count来存储节点所属的简单路径的数量；两者都初始化为零。

对于每个节点，从根开始：

  • 如果不是所有的孩子都被探访过，那就去找一个没有探视过的孩子。
  • 如果所有子节点都已被访问（或节点是叶子节点）：
    • 增加child_count。
    • 用 N - child_count增加path_count。
    • 将此节点的path_count × cost添加到总成本中。
    • 如果当前节点是根节点，我们就完成了；否则：
      • 使用此节点的child_count增加父节点的child_count。
      • 用该节点的child_count × (N - child_count )增加父节点的path_count。
      • 转到父节点。
于 2017-07-23T03:27:13.867 回答
-1

以下算法的运行时间为 O(n^3)。

树是没有环的强连通图。因此，当我们想要获得所有可能的对的成本时，我们试图找到所有对的最短路径。因此，我们可以使用 Dijkstra 的想法和动态规划方法来解决这个问题（我从 Weiss 的书中得到它）。然后我们将 Fibonacci 函数应用于成本，假设我们已经有一个表要查找。

  • Dijkstra 的想法：我们从根开始，搜索从根到所有其他节点的所有简单路径，然后对图上的其他顶点执行此操作。
  • 动态规划方法：我们使用二维矩阵 D[][] 来表示节点 i 和节点 j 之间的最低路径/成本（它们可以互换使用。）。最初，已经设置了 D[i][i]。如果节点 i 和节点 j 是父/子，则 D[i][j] = g(i, j)，即它们之间的成本。如果节点 k 在节点 i 和节点 j 成本较低的路径上，我们可以更新 D[i][j]，即 D[i][j] = D[i][k] + D[ k][j] 如果 D[i][j] < D[i][k] + D[k][j] 否则 D[i][j]。

完成后，我们检查 D[][] 矩阵并将斐波那契函数应用于每个单元格并将它们相加，并应用模运算。

于 2017-07-26T18:56:46.400 回答