问题标签 [lowest-common-ancestor]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
binary-tree - 如何找到二叉树中所有节点对的 LCA
有一些算法可以找到给定节点对的 LCA。但是是否有任何算法可以在小于 O(n^2) 的渐近时间内找到二叉树中所有节点对的 LCA？
我正在专门寻找时间跨度为 O(n log n) 的算法
c++ - 在c ++中找到两个向量中第一个公共条目的位置的最快方法是什么？
我有两个向量u = {32, 25, 13, 42, 55, 33}，v = {18, 72, 53, 39, 13, 12, 28}我想确定它们的第一个公共条目的位置，13。对于这些示例向量，这些位置是 3 和 5。找到这些位置的最快方法是什么？我必须多次执行此操作。
graph - 查找树中两个节点之间的深度差异，而不是一直到根
我遇到了一个我无法弄清楚的问题。
假设一棵二叉树，其中每个节点都有一个指向其父节点的指针和两个子节点。我们接收 r、p、q（根和树中的两个节点）的输入，我们想要找到 p 和 q 之间的深度差，而不需要一直遍历到根。
限制和假设：
- 没有内存使用（意味着没有数组，变量都可以）
- 假设节点 Lowest Common Ancestor 不是根（为了简单起见，我们假设 LCA 远离 Big-O 表示法中的根。
只是为了澄清 - 基本上，问题是我们如何在不一直到根部且没有记忆的情况下找出深度差异。
谢谢！
python-3.x - 最低共同祖先中的 Python3 语法
BT 中 LCA 的经典问题：给定二叉树，找到最低的共同祖先。我找到了一个 Python2 解决方案，但不知道如何在 Python3 中修复它。
我是 Python3 的新手，并试图在 Python3 中修复这个错误，我正在尝试下面，但没有工作。
algorithm - 查询从 U 到 V 行驶所需的最低燃料
问题：
给定一棵有 N 个节点的树。
树的每条边包含：
D: 边的长度T：通过该边缘所需支付的金币（应在通过该边缘之前支付金币）
通过边缘移动时，如果您携带X金币，则需要X*D燃料。
有两种类型的查询：
- u, v：找到将
G黄金从 u 转移到 v 所需的燃料（G在所有查询中都是固定的） - u, v, x：更新到 x
T的边{u,v}（{u, v}保证在树中）
约束：
例子：
以查询 1 和u = 3和v = 6为例。首先，您从 开始3，支付 2，拥有 9，然后使用燃料11 golds前往节点 2 。接下来，我们支付 3 枚金币，有 6 枚，然后带着燃料9*1 = 9前往节点 4 。最后，我们支付 4，拥有 2 金币，然后带着燃料6*2 = 12前往节点 6 。2*1 = 2所以需要的燃料是9 + 12 + 2 = 23.
所以查询的答案是：u = 3, v = 623
第二个查询只是更新T边缘，所以我认为没有必要解释。
我的看法
我只能在 O(N*Q) 中解决问题。由于它是一棵树，从 u 到 v 只有 1 条路径，因此对于每个查询，我执行 DFS 来查找从 u 到 v 所需的燃料。这是该子任务的代码：https ://ideone.com/ SYINTQ
对于一些全部T为 0 的特殊情况。我们只需要找到 from uto的长度v并乘以 G。使用距离数组和 LCA 可以很容易地找到from uto的长度。v我认为这可能是正确解决方案的提示。
有没有办法在 logN 或更少的时间内进行查询？
P/S：如果有什么需要澄清的地方请评论，并为我的英语不好感到抱歉。