Find LCA in a tree and extend to a DAG

Part A — LCA variant in a rooted tree

You are given a rooted tree with n nodes labeled 0..n-1.

Input:

• parent[i] for each node i ( parent[root] = -1 ).
• Two nodes u and v .

Task:

• Return the lowest common ancestor (LCA) of u and v .

Clarifications:

• The LCA is the common ancestor with the greatest depth.
• The input always forms a valid tree.

Follow-up (variant):

• Answer multiple queries q (up to ~1e5) for different pairs (u, v) efficiently.

Part B — Follow-up: generalize to a DAG

Now the structure is a directed acyclic graph (DAG) where edges point from a node to its parent(s) (a node may have multiple parents).

Input:

• parents[i] : list of parent nodes of i (possibly empty).
• Two nodes u and v .

Task:

• Return the set of lowest common ancestors of u and v in the DAG, defined as:
  • Nodes that are ancestors of both u and v , and
  • Do not have any descendant (within the common-ancestor set) that is also a common ancestor.

Notes:

• In a DAG, there may be multiple lowest common ancestors.

Constraints (reasonable interview constraints)

• n up to ~2e5, edges up to ~5e5.
• DAG is guaranteed acyclic.
• Aim for near-linear preprocessing for many queries when applicable.