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

There will be many queries. Each query (A,B,K) requires you to check if a node (value=K) can be found in the path from A to B. Solution is expected not to exceed O(n+qlogq), n,q : node count, queries count.

I have a solution in my mind. I am posting that down. I want to know what other approaches are.

my approach:

Find LCA (lowest common ancestor) between A and B. Check if K is an ancestor to A or B. If yes=> check if LCA is ancestor to K. If yes, output yes. To find if a vertex is ancestor to other vertex, we can check whether a vertex is present in the subtree of another vertex. (This can be done in O(1) if we preprocess node's in-out visiting order in dfs. https://www.geeksforgeeks.org/printing-pre-and-post-visited-times-in-dfs-of-a-graph/ )

But the complexity increases if all queries have same K value. we need to check all the K which satisfies the in-out times with A or B. So to optimize that we can sort all K respective to in-out time of DFS.

Any thoughts?

Solution 1:

There are following cases for R to exist in the path between U and V:

1. R is the lowest common ancestor of U and V.
2. R is on the path between LCA(U,V) and U.
3. R is on the path between LCA(U,V) and 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;
}