问题标签 [lowest-common-ancestor]

我试图学习 LCA 算法O(nlog n) 预处理和 O(log n) 查询。我在谷歌翻译的帮助下从一个俄罗斯网站阅读它。但它翻译得不好，我很难理解它. 有人可以帮我吗？

这是我从该网站获取的伪代码

我所了解的

• 我知道我们正在遍历图形并存储每个顶点的时间和时间。

• 我明白什么up[i][j]是顶点的2^j祖先。i

• 我明白为什么up[v][0]=p（因为2^0即顶点的第一个祖先v只是它的父亲）

• 我了解上层函数的作用。它决定了哪个顶点出现在A或之前B。

• 我知道上层(a,b)比 lca 更真实A，同样是第二步。

我在伪代码中提到了我不明白的内容。请帮助我并确认我是否理解了所有内容。

PS->对不起我的英语。对此不太满意。

我的问题非常直截了当。

给出了一个加权树。我们必须找到两个给定节点之间的距离。

因为每次 bfs 超时时查询的数量都非常高（大约 75000），所以我尝试了不同的方法来做到这一点。

我的算法是这样的：

• 我从顶点0运行dfs并计算从root（0）到所有顶点的距离，就像这样

  /li>

• 一旦我使用 dfs 和每个节点的第 2^j 个父节点计算了所有节点的深度（假设我知道该怎么做）。我计算了每个查询的 (u,v) 的 LCA 。

• 然后我像这样计算距离

  /li>

但我没有得到预期的正确判决。我的算法是正确的还是我错过了一些重要的东西。需要指导:)

Ps 万一有人想看我的实现-链接http://paste.ubuntu.com/13129038/

我使用数组编写了一个非常简单的树类。此类需要表示链接在一起的数据，但它们可以具有不同数量的连接（即，一条路径可能只有 3 个节点，而另一条路径可能有 10 个节点）。话虽如此，我需要找出一种可能的解决方案来使用具有多个叶索引的此类执行 LCA。这是我到目前为止写的代码：

在此先感谢，干杯，

乔瓦尼

假设我们有这个父/子层次结构：

什么是 Clojure 惯用的实现在这种层次结构中找到最低共同祖先的方法？IE：

我最初的想法包括使用递归函数遍历parents每个参数的组合，但我怀疑可能有更好的方法。

我的动机是将其用作多方法的分派函数，该方法采用 2 个参数并根据参数的类型分派到最适合的实现。

给定一棵树，我需要在从“a”到“b”的路径中找到第“k”个节点。这意味着我需要在从节点'a'到节点'b'的路径中的'kth'位置找到节点。我在考虑最低共同祖先和/或重光分解的路线，但我不确定这是否是这样做的方法。任何正确方向的指导表示赞赏。

细节：

• 这棵树不是二叉树。这是一个无向图，有 n-1 条边，n 个顶点，没有环。只是你的普通树
• 这棵树的顶点编号从 1 到 n。有 n-1 条无向边连接 n-1 对这些顶点
• 'a' 和 'b' 是树中从 1 到 n 编号的任意 2 个顶点。我们要在从“a”到“b”的路径中找到第“k”个节点。保证 'k' 的值 <= 从 'a' 到 'b' 的路径中的节点数

BFS 应用于每个查询（从“a”到“b”的第 k 个节点）不是一个选项，因为查询的数量很大。

我已经编写了这个解决方案来查找二叉树的 LCA。它给出了更大输入的时间限制。有人可以指出这段代码中的一个问题。这个问题来自 Leetcode OJ。

我正在尝试使用 graphrepository 在 spring-neo4j 中创建一个应用程序。其中一个要求是在两个子节点之间找到一个最低公共祖先 (lca)。

目前我使用以下查询来实现这一点：

这里的问题是性能。最初我的图表由 330 000 个节点和 2 000 000 个关系组成。我感兴趣的关系是具有类型的关系：“Is a”。它们仅在树中向上移动（连接子节点与父节点）。最大向上距离为 3。

这是树结构：

因为我有几个像这样的树结构，所以我决定添加一个根节点，将所有不同的树结构连接在一起。以便始终找到 lca。但是添加这个根节点极大地改变了我的性能：从 558 毫秒到 562286 毫秒

我知道添加根节点会影响性能，但它不应该这么多，对吧？如果是这样，是否有更好的方法来计算 lca？

我认为我的密码查询只会在树中向上查找节点。所以在这种情况下，添加一个额外的根节点不应该对性能产生这么大的影响。

该问题基于最低共同祖先概念。
它需要在树中的一对节点之间的路径中找到最短和最长边的长度。
这是问题的链接：SPOJ DISQUERY

给定一棵树，N其中每条边都有权重的顶点1。节点用C颜色着色。对于每种颜色，我们希望找到该颜色的两个节点之间的最大最短距离。

我可以建立一个稀疏表，然后在O(log n). 然后检查所有相同颜色的对。这给了O(n^2 log n). 有可能做得比这更好吗？

我正在尝试合并多行字符串。我已经编写了用于合并没有“/n”字符但无法继续进行的数据的代码。我需要实现的是，将祖先节点与远程节点和本地节点进行比较，并逐行合并祖先节点中远程或本地的更改。每一行都应该在和更新之间进行比较$ancestor->$remote和$ancestor->$local更新祖先。

例如：第 3 行在远程而不是本地更改，因此第 3 行的所有更改都$remote应该合并到 $ancestor 中，$local如果第 6 行有更改，第 6 行也应该发生相同的情况。

另一个例子：