algorithm - 使用 n*log(n) 算法预处理树

Question

这是一道作业题:

在O(n*log(n))中使用一个预处理算法，然后在O(1)中描述算法来回答这个问题:“whether节点 u 是节点 v 的祖先？”

实际上我想不出比 O(log(n)) 更好的算法。

Answer 1

在 O(n*log(n)) 中，您可以为每个节点提供其自身祖先的列表，返回到根。在 O(1) 中，一个节点然后可以回答“你离根有多远？”这样的问题之一。和“你的哪个祖先距离根有 k 的距离？”。