给定一个有n个节点的根树，其中所有叶子都从一组标签中标记。构建一个数据结构，在给定叶节点a和标签l的情况下，可以找到a的最低祖先u，其中u至少有一个带有标签l的子代。
这具有时间复杂度O（n）和空间复杂度O（n）。
对于线性空间复杂度，有没有更快的方法？也许通过某种方式对树进行预处理？l和a不是固定的，因此预处理必须灵活。
最低的共同祖先可以在常数时间内使用RMQ通过欧拉旅行找到。
请记住，树不是以任何方式平衡或排序的。
所以，现在我找到了一个更好的解决方案：
想法如下：欧拉路径中出现的越远的两个节点，它们的LCA越高。即index（a）
这意味着您只需计算路径中带有标签l的a和a之后的第一个节点的LCA，以及路径中带有标签l的a和a之前的最后一个节点的LCA。
其中之一将给出问题的最佳解决方案。
要有效地找到这两个索引，请为每个标签创建一个索引列表，并在O（log n）中执行二分查找。
存储器复杂度为O（n）。
这是一个时间复杂度为O（log（n）^3，空间复杂度为O（n log（n））的解。
让L成为您在欧拉路径上遇到的标签列表。您使用此列表构建一个段树，并在树的每个节点中存储出现在相应段中的标签集。然后您可以通过段树中的范围查询检查O（log（n）^2）时间，如果标签出现在子树中。
要找到正确的父母，你可以做二分搜索法。例如类似于二进制提升的东西。这将增加log(n)的另一个因子。
