问题标签 [lowest-common-ancestor]

我看到了类似的帖子：如何从依赖解析器的输出中生成树？人们帮助我获得了从根到叶的路径。我想找到两个单词的最低共同祖先，因为我想找到两个节点之间的路径。

到目前为止，我有这个：

类别：

当我打电话时lowestcommonancestor(categories,'fuck','U')，我得到week了哪个是U但不是的父母fuck。因此，我应该arrested作为节点。

我无法完成该功能，并且我认为我没有返回正确的节点。请帮忙。

我正在使用使用 RMQ 在树中解决 LCA 的算法。

它基本上是这样工作的：

• 我们在树上执行欧拉之旅，得到 3 个数组

  /li>

• 如果我们想要LCA(u,v)，我们只需要获取LfromI[u]到的 RMQ I[v]。

I[1] = 1例如： LCA(1,2) = 从索引到的 L 的 RMQ I[2] = 3。

L[1:3] = [1,0,1], RMQ[1,0,1] = 0，即索引 2，因此LCA(1,2) = E[2] = 0。

我的问题是：如何扩展此解决方案以适应有向无环图？

就这样，行不通。假设我们有这个 DAG：

如果我们计算E,L和I，我们将有：

并且可以看出它是错误的证明计算 LCA(2,4)，这显然应该是 2，因为 2 是 4 的父级，但是按照算法，我们将计算：

RMQ( I[2] : I[4] ) = RMQ(7,4) = RMQ(4,7) = RMQ( {2,1,0,1} ) = 0

0 有索引 6，所以LCA(2,4) = E[6] = 0，这是错误的。

有没有办法让它工作？

二叉树

考虑到我们允许一个节点是它自己的后代，那么上面二叉树中 5 和 4 的最低共同祖先是什么。不会是3吗？如果不是，那会是什么，为什么？

我有一个需要用于分析的节点层次结构。有点像这样

我正在尝试找到一种算法，使我能够找到两个节点之间最近的共同祖先。我知道有一些算法可以找到最低的共同祖先，但我还没有找到一个可以让我们找到最近的几个的算法。

例如，在我上面链接的图片中，如果我给它两个节点：0 和 1，它应该返回 2 和 5。即它应该返回没有后代的节点的所有共同祖先也是共同祖先。一种天真的方法是获取 0 和 1 的所有共同祖先：{7, 5, 6, 3, 2}，然后消除 7，因为它在集合中有后代。然后它也会消除 6 和 3。所以它会返回 SLCA = {5,2}。目前，我已将每个节点的所有祖先存储在一个列表中。所以这种天真的方法是可能的。但是，我想做一个更有效的方法，即使是非常大的图也可以扩展。最终，对于给定的图，我希望能够计算每对节点的成对 SLCA。我认为这种蛮力方法对于非常大的图表会很慢。

有人知道这样的算法吗？我一直在阅读这些论文，但它们非常密集，我一直在努力理解它们。

https://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/LCA-Max-witness.pdf

http://www.ccs.neu.edu/home/dherman/browse/projects/mini-javac/papers/bender01finding.pdf

https://algo2.iti.kit.edu/download/fischer10new.pdf

https://algo2.iti.kit.edu/download/fischer10new.pdf

我很感激帮助

我正在研究这个挑战：

给定一棵具有N个节点和N-1 条边的树。树上的每条边都由一串来自拉丁字母的小写字母标记。给定由两个节点u和v组成的Q个查询，检查是否有可能创建一个回文字符串，该字符串使用属于从节点u到节点v的路径中的边上标记的字符串的所有字符。

字符可以按任何顺序使用。

N为 10 ⁵的数量级，Q为 10 ^{6的数量级}

输入：

N=3
u=1 v=3 权重=bc
u=1 v=2 权重=aba
Q=4
u=1 v=2
u=2 v=3
u=3 v=1
u=3 v=3

输出：

是
是
否
否

我的想法是通过在欧拉塔上使用稀疏表和 Range 最小查询在O(1)中进行预计算来计算 2 个节点之间的 LCA，然后查看从 LCA 到节点 u 和 LCA 到节点 v 的路径并存储所有字符频率。如果所有字符的频率之和为奇数，我们检查除一个之外的每个字符的频率是否为奇数。如果所有字符的频率之和是偶数，我们检查每个字符的频率是否是偶数。但是这个过程肯定会超时，因为Q可以达到 10 ⁶。

有人有更好的算法吗？

在尝试解决这个问题时，我在 Leetcode 上找到了这个解决方案：

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Leetcode 上的每个人似乎都理所当然地认为这是如何工作的。但我不明白。这里发生了什么，这是使用什么算法来查找二叉树的 LCA？

我怎样才能得到这个生成器的输出？out.next()或next(out)不起作用：

因此，我试图使用最基本的方法来解决以下问题，即存储路径和查找 LCA。我的代码在 VSCode 上运行良好并提供了正确的输出。但是在SPOJ上提交时，它会给出运行时错误（SIGSEGV）。

问题链接：https ://www.spoj.com/problems/LCA/

问题描述：

树是一个无向图，其中任何两个顶点都通过一个简单的路径连接。换句话说，任何没有环的连通图都是一棵树。- 维基百科

最低共同祖先（LCA）是图论和计算机科学中的一个概念。令 T 为具有 N 个节点的有根树。最低共同祖先定义在两个节点 v 和 w 之间，作为 T 中同时具有 v 和 w 作为后代的最低节点（我们允许一个节点成为其自身的后代）。- 维基百科

你在这个问题中的任务是找到给定树 T 中任意两个给定节点 v 和 w 的 LCA。

样本输入：

样本输出：

我的代码：

我认为我没有访问任何超出范围的元素，因此不应出现 SIGSEGV。
请告诉我如何修复和改进我的代码。

我已经实现了 LCA 问题的解决方案。问题陈述是给定一棵二叉树，找到树中两个给定节点的最低共同祖先（LCA）。我使用的方法是找到从根到给定 2 个节点的路径，并将 2 个路径存储在一个向量中。从根开始比较两条路径中的节点（直到 LCA 应该匹配 p 和 q 的路径），所以在路径中发生不匹配之前的节点将是 LCA。

但是 Leetcode 仅通过了 29/31 个测试用例，对于非常大的输入超出了时间限制。这是代码：

据我所知，时间复杂度为 O(N)。不明白为什么我会得到 TLE。

这是我很难解决的问题。

给定一个密文 Y 和从字符串 Z 产生 Y 的循环移位序列，带有参数 (i, j, k) 的移位适用于子字符串 Z[i..j]（从第 i 个到 j- th 字符，包括）并循环向右旋转 k 次。字符串字符从 1 开始编号。鉴于上述信息，您的任务是猜测初始明文 X。

输入：

第一行包含密文，它是一个由 N 个小写英文字母（1 ≤ N ≤ 50000）组成的非空字符串。第二行包含班次数 M (1 ≤ M ≤ 50000)。以下 M 行描述了循环移位的序列（按照它们应用于明文的顺序）。每个移位由三个参数 i、j、k (1 ≤ i < j ≤ N, 1 ≤ k ≤ j - i) 描述。

输入示例：

作为输出，您应该提供解密的文本（例如“goodluck”）。

显而易见的方法是尝试从最后一个班次开始反转每个班次。这种方法似乎不省时。但是，我无法想出如何以其他方式做到这一点的任何想法，因此不胜感激。

我附上我的代码：