检查树中从 A 到 B 的路径中是否存在节点

Question

会有很多查询。每个查询 (A,B,K) 都要求您检查是否可以在从 A 到 B 的路径中找到一个节点 (value=K)。解决方案预计不会超过 O(n+qlogq), n,q : node计数，查询计数。

我心里有办法。我把它贴下来了。我想知道其他方法是什么。

我的做法：

查找A和B之间的LCA（最低共同祖先）。检查K是否是A或B的祖先。如果是=>检查LCA是否是K的祖先。如果是，则输出是。要确定一个顶点是否是其他顶点的祖先，我们可以检查一个顶点是否存在于另一个顶点的子树中。（如果我们在 dfs 中预处理节点的 in-out 访问顺序，这可以在 O(1) 中完成。https://www.geeksforgeeks.org/printing-pre-and-post-visited-times-in-dfs-of-a-graph/ ）

但是如果所有查询都具有相同的 K 值，则复杂度会增加。我们需要检查所有满足 A 或 B 的进出时间的 K。因此优化我们可以对所有 K 分别根据 DFS 的进出时间进行排序。

有什么想法吗？

Answer 1

R存在于U和V之间的路径中有以下几种情况：

R 是 U 和 V 的最低共同祖先。
R 在 LCA(U,V) 和 U 之间的路径上。
R 在 LCA(U,V) 和 V 之间的路径上。

// Function that return true if R
// exists on the path between U
// and V in the given tree
bool isPresent(int U, int V, int R)
{
 
  // Calculating LCA between U and V
  int LCA = lowestCommonAncestor(U, V);
 
  // Calculating LCA between U and R
  int LCA_1 = lowestCommonAncestor(U, R);
 
  // Calculating LCA between U and V
  int LCA_2 = lowestCommonAncestor(V, R);
 
  if (LCA == R || (LCA_1 == LCA && LCA_2 == R) ||
      (LCA_2 == LCA && LCA_1 == R)) {
    return true;
  }
  return false;
}

检查树中从 A 到 B 的路径中是否存在节点

Check if a node is present in Path from A to B in tree

algorithm

tree