问题标签 [lowest-common-ancestor]

我正在尝试解决一个问题，该问题需要我确定节点 w 是否位于树中节点 u 和节点 v 之间的路径上（不一定是二元的）。

例如，对于以下树：

节点 2 位于从节点 4 到 7 的路径上。

一个明显的解决方案是获得树的欧拉之旅并遍历两个节点第一次出现之间访问过的节点。但是，在最坏的情况下，这将是一个 O(n) 解决方案，其中 n 是树中的节点数。我在某处读到这可以使用 LCA（最低共同祖先）来完成。但是，我似乎无法理解如何。有人可以给我建议吗？

问题：

给你一棵树，它有n 个节点（最多可达 10^5）和n-1 个双向边。假设每个节点包含两个值：

1. 它是索引（只是节点的唯一编号），可以说它是从 1 到 n。
2. 它的值Vi，可以在1 到 10^8之间变化

现在在同一棵树上将有多个相同类型的查询（查询数可以达到 10^5），如下所示：

1. 您将获得 node1、node2 和一个值P（可以在1 到 10^8之间变化）。

对于每一种此类查询，您只需找到从 node1 到 node2 的路径中其值小于 P的节点数。

注意：所有节点之间会有唯一的路径，并且没有两条边属于同一对节点。

所需的时间复杂度 O(nLog(n)) 或者可以用其他术语表示，但在给定的约束条件下应该可以在 1 秒内解决。

我试过的：

（一个）。如果 P 的值是固定的，我可以很容易地解决它，使用 O(nLog(n)) 中的 LCA 方法，通过在每个节点存储以下信息：

1. 从根到给定节点的值小于 P 的节点数。

但是这里的 P 变化太大，所以这无济于事。

（乙）。我在想的其他方法是使用简单的 DFS。但这也需要 O(nq)，其中 q 是查询数。同样，因为 n 和 q 都在 1 到 10^5 之间变化，所以这在给定的时间限制下也无济于事。

我想不出别的了。任何帮助，将不胜感激。:)

资源：

我猜我在 SPOJ 的某个地方读到了这个问题。但是现在找不到了。尝试在 Web 上搜索它，但在任何地方都找不到解决方案（Codeforces、CodeChef、SPOJ、StackOverflow）。

给定一棵带有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配对有明显的改进，但这仍然是二次的。

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

我已经加载了 DNA SNP 的分层树 (DAG)。我想确定最低的共同祖先。

此查询有效，产生单个正确节点：

但是，这没有产生任何结果：

即使寻找两个收益节点的祖先的两个查询，其中一些是共享的：

和

似乎问题在于 R-Z11 在第二个查询的路径中，并且它本身就是祖先。换句话说，有时 LCA 处于最短路径的末端。有没有办法解决这个问题，以便 R-Z11 作为结果返回它是否在最短路径中？

你有两个节点p，q你如何找到最低的共同祖先？（假设它们都属于一棵非常大的树）

您没有参考树的根。

最有效的方法是什么？到目前为止，我唯一的想法是

(1) 选择一个节点 p（不管哪个）

(2)搜索p的左子树，如果看到q，返回p

(3) else搜索p的右子树，如果看到q，返回p

(4) else 上一级 parent 查找不包含 p 的子树，如果找到 q，则返回 parent

(5) else，再上一级，重复(4)（搜索不包含这个父节点的子树）

这似乎效率极低。有更好的算法吗？

我想编写一个适用于一些树状结构数据的工具。（事实上​​，它可以在 git 修订 DAG 的树状子集上工作，但这对于这个问题并不重要）。特别是我想要一种算法来重建由给定输入集的所有“连接点”组成的树的子集。

具体来说，我认为我想要的是

• 我们有一些H具有“最低共同祖先”功能的类型lca。这给出H了树状结构。

• 该算法将某些子集S作为H输入。

• 输出应该是一个多路树t，其节点由 的值标记H。

• t应该满足性质

  • 全部s在S标签的某个节点中t

  • 的叶子t只能由元素标记S

  • h标签的任何元素H不超过一个节点t

  • 如果h1标签n1和h2标签n2则标记和inlca(h1, h2)的最低共同祖先。n1n2t

我的问题是：“这是已知算法的已知问题吗？”。我怀疑是这样。它似乎与拓扑排序非常相似。我有一个基于合并排序的算法的想法，但如果已知算法已经存在，那么没有理由想出我自己的算法。

我有兴趣计算有向图中几个节点的最低共同祖先。我测试了 jGrapht 项目的 NaiveLcaFinder 类提出的 findlcas 方法（https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/NaiveLcaFinder.java ) 但我发现很难将它应用于多个节点。你能帮我解决这个问题吗？或者给我一些建议

-- 下面的函数在二叉树中lowestCommonAncestor找到两个节点的最低共同祖先p和（假设两个节点都存在并且所有节点值都是唯一的）。q

问题

给定具有n 个节点的有根树，其中所有叶子都从一组标签中标记出来。构建一个数据结构，给定叶节点a和标签l，可以找到 a 的最低祖先u，其中u至少有一个标签为l的后代。

线性空间/线性时间方法

• 从叶a开始
• 检查a 的所有兄弟姐妹
  • 如果一个兄弟姐妹有标签l找到a和那个兄弟姐妹之间的最低共同祖先。
  • 否则继续父母
• 如果所有从父母下来的叶节点都没有标记为l，则继续到祖父母并检查它们的叶节点后代。
• 继续递归检查大祖父母及其所有后代叶节点，直到找到带有l标记的后代。

这具有时间复杂度O(n)和空间复杂度O(n)。

有没有更快的方法来处理线性空间复杂度？也许通过某种方式对树进行预处理？l和a不是固定的，因此预处理必须灵活。

可以通过 Eulerian-Tour 使用 RMQ 在恒定时间内找到最低的共同祖先。

请记住，树不平衡或以任何方式排序。

[1]：https ://www.geeksforgeeks.org/lca-for-general-or-n-ary-trees-sparse-matrix-dp-approach-onlogn-ologn/

在上面的代码中，当“(diff>>i)”为奇数时，它只跳转到第 2^ith 父级。为什么会这样？我们如何理解只有在奇数“（diff>>i）”的情况下，我们才必须跳转？