algorithm - 如何找到具有某个标签的后代叶节点的最低祖先？

Question

问题

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

线性空间/线性时间方法

• 从叶子a开始
• 检查a的所有 sibling
  • 如果一个 sibling 有标签l，找到a和那个 sibling 之间的最小共同祖先。
  • 否则继续给 parent
• 如果从父代传下来的所有叶节点都没有被标记为l，则继续到祖 parent 并检查它们的叶节点后代。
• 继续递归检查曾祖 parent 及其所有后代叶节点，直到找到标记为 l 的后代。

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

---

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

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

请记住，这棵树不是平衡的，也不是以任何方式排序的。

Answer 1

所以，现在我找到了一个更好的解决方案:

思路如下:欧拉路径中出现的节点越多，它们的 LCA 就越高。IE。 index(a) < index(b) < index(c) => dist_to_root(LCA(a, b)) >= dist_to_root(LCA(a, c)) .

这意味着您只需计算a 和路径中a 之后带有标签l 的第一个节点的LCA，以及a和a之前的最后一个节点的LCA，路径中标签为l。

其中一个将给出问题的最优解。

要有效地找到这两个索引，请为每个标签创建一个索引列表，并在 O(log n) 中执行二进制搜索。

内存复杂度为O(n)。