algorithm - 树上的斐波那契和

Question

给定一棵具有 n 个节点的树(n 可以和 2 * 10^5 一样大)，其中每个节点都有一个成本与之相关，让我们定义以下函数:

• g(u, v) = 从 u 到 v 的简单路径上所有成本的总和
• f(n) = 第 (n + 1) 个斐波那契数(n + 1 不是错字)

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

举个例子，我们以一棵有 3 个节点的树为例。

• 不失一般性，假设节点 1 是根节点，其子节点是 2 和 3
• 成本[1] = 2，成本[2] = 1，成本[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 作为正确答案。

---

我的尝试:

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

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

现在是非常棘手的部分。无论我如何进行上述计算，在计算所有可能的 f(g(u, v)) 。我的意思是只有 n * (n - 1)/2 对有明显的改进，但这仍然是二次的。

我错过了什么？我已经研究了好几个小时了，但我无法在不实际生成二次算法的情况下找到求和的方法。

Answer 1

要知道节点 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 都被拜访过，那就去找一个未被拜访过的 child 。
• 如果所有子节点都被访问过(或者节点是叶节点):
  • 增加 child_count。
  • 将 path_count 增加 N - child_count。
  • 将此节点的path_count × cost 添加到总成本中。
  • 如果当前节点是根节点，我们就完成了；否则:
    • 用本节点的 child_count 增加父节点的 child_count。
    • 用本节点的child_count × (N - child_count) 增加父节点的path_count。
    • 转到父节点。