如何找到具有某个标签的后代叶节点的最低祖先？
How does one find the lowest ancestor with a descendant leaf node with some label?
问题
给定一棵具有 n 个节点的有根树，其中所有叶子都由一组标签标记。构建一个数据结构，给定一个叶节点 a 和一个标签 l，可以找到最低的祖先 u[= a 的 50=]，其中 u 至少有一个带有标签 l 的后代。
线性Space/线性时间方法
- 从叶开始 a
- 检查 a 的所有兄弟姐妹
- 如果兄弟姐妹有标签 l 找到 a 和那个兄弟姐妹之间的 lowest-common-ancestor。
- 否则继续parents
- 如果所有 parents 的后代 leaf-nodes 都没有被标记为 l，请继续到 grandparents 并检查它们的 leaf-node后代。
- 继续递归检查 greater-grandparents 及其所有后代 leaf-nodes，直到找到 l 标记的后代。
这具有时间复杂度 O(n) 和 space 复杂度 O(n).
有没有更快速的线性 space 复杂度的方法？也许通过某种方式预处理树？ l 和 a 不是固定的，所以 pre-processing 必须是灵活的。
可以通过 Eulerian-Tour.
使用 RMQ 在常数时间内找到最低的共同祖先
请记住，树不是平衡的，也不是以任何方式排序的。
这是一个 O(log(n)^3) 时间复杂度和 O(n log(n)) 的解决方案space 复杂度。
设 L 为您在欧拉路径上遇到的标签列表。您使用此列表构建一个线段树，并在树的每个节点中存储出现在相应线段中的标签集。
然后你可以检查 O(log(n)^2) 时间，如果一个标签通过线段树中的范围查询出现在子树中。
要找到正确的父级，您可以进行二分查找。例如。类似于二进制提升的东西。这将增加 log(n).
的另一个因素
所以，现在我找到了更好的解决方案：
思路如下：
欧拉路径中出现的节点越多，它们的 LCA 就越高。
IE。 index(a) < index(b) < index(c) => dist_to_root(LCA(a, b)) >= dist_to_root(LCA(a, c))。
这意味着你只需要计算 a 和 a 之后的第一个节点的 LCA，标签为 [=24=路径中的]l，以及a和a之前的最后一个节点的LCA，标签为 l在路径中.
其中一个会给出问题的最优解。
为了有效地找到这两个索引，为每个标签创建一个索引列表，并在 O(log n).
中执行二进制搜索
内存复杂度为 O(n)。
问题
给定一棵具有 n 个节点的有根树，其中所有叶子都由一组标签标记。构建一个数据结构，给定一个叶节点 a 和一个标签 l，可以找到最低的祖先 u[= a 的 50=]，其中 u 至少有一个带有标签 l 的后代。
线性Space/线性时间方法
- 从叶开始 a
- 检查 a 的所有兄弟姐妹
- 如果兄弟姐妹有标签 l 找到 a 和那个兄弟姐妹之间的 lowest-common-ancestor。
- 否则继续parents
- 如果所有 parents 的后代 leaf-nodes 都没有被标记为 l，请继续到 grandparents 并检查它们的 leaf-node后代。
- 继续递归检查 greater-grandparents 及其所有后代 leaf-nodes，直到找到 l 标记的后代。
这具有时间复杂度 O(n) 和 space 复杂度 O(n).
有没有更快速的线性 space 复杂度的方法？也许通过某种方式预处理树？ l 和 a 不是固定的，所以 pre-processing 必须是灵活的。
可以通过 Eulerian-Tour.
使用 RMQ 在常数时间内找到最低的共同祖先请记住，树不是平衡的，也不是以任何方式排序的。
这是一个 O(log(n)^3) 时间复杂度和 O(n log(n)) 的解决方案space 复杂度。
设 L 为您在欧拉路径上遇到的标签列表。您使用此列表构建一个线段树，并在树的每个节点中存储出现在相应线段中的标签集。
然后你可以检查 O(log(n)^2) 时间，如果一个标签通过线段树中的范围查询出现在子树中。
要找到正确的父级，您可以进行二分查找。例如。类似于二进制提升的东西。这将增加 log(n).
的另一个因素所以，现在我找到了更好的解决方案：
思路如下：
欧拉路径中出现的节点越多，它们的 LCA 就越高。
IE。 index(a) < index(b) < index(c) => dist_to_root(LCA(a, b)) >= dist_to_root(LCA(a, c))。
这意味着你只需要计算 a 和 a 之后的第一个节点的 LCA，标签为 [=24=路径中的]l，以及a和a之前的最后一个节点的LCA，标签为 l在路径中.
其中一个会给出问题的最优解。
为了有效地找到这两个索引，为每个标签创建一个索引列表，并在 O(log n).
中执行二进制搜索内存复杂度为 O(n)。