algorithm - 如何确定节点 w 是否位于树中节点 u 和节点 v 之间的路径上？

Question

我正在尝试解决一个问题，该问题需要我确定节点 w 是否位于树中节点 u 和节点 v 之间的路径上（不一定是二元的）。

例如，对于以下树：

    1
  2   3
4  5 6  7

节点 2 位于从节点 4 到 7 的路径上。

一个明显的解决方案是获得树的欧拉之旅并遍历两个节点第一次出现之间访问过的节点。但是，在最坏的情况下，这将是一个 O(n) 解决方案，其中 n 是树中的节点数。我在某处读到这可以使用 LCA（最低共同祖先）来完成。但是，我似乎无法理解如何。有人可以给我建议吗？

Answer 1

假设 A = LCA(u,v)。u 和 v 之间的路径是从 u 到 A 和从 A 到 v 的路径。检查每个节点（从 u 向上然后从 v 向上）。如果 w 在其中，则它在路径上，否则不在。