FastPrep
Problem · Tree

Tree Ancestor Queries

Learn this problem
● MediumArcesiumFULLTIMEONSITE INTERVIEW

Problem statement

You are given a rooted tree as directed parent-to-child edges and a list of queries.

For each query [x, y], determine whether node x is an ancestor of node y. A node is an ancestor of another node if it can reach that node by following one or more child edges.

Return an integer array where the ith value is 1 when the answer for the ith query is true, and 0 otherwise.

Function

answerAncestorQueries(edges: int[][], queries: int[][]) → int[]

Examples

Example 1

edges = [[1,2],[1,3],[2,4],[2,5],[3,6],[5,7]]queries = [[1,6],[6,1],[2,7],[2,6]]return = [1,0,1,0]

Node 1 is an ancestor of 6; node 6 is not an ancestor of 1; node 2 is an ancestor of 7; and node 2 is not an ancestor of 6.

Constraints

  • 1 <= edges.length + 1 <= 10^5
  • 1 <= queries.length <= 10^5
  • The input edges form a rooted tree.

More Arcesium problems

drafts saved locally
public int[] answerAncestorQueries(int[][] edges, int[][] queries) {
  // write your code here
}
edges[[1,2],[1,3],[2,4],[2,5],[3,6],[5,7]]
queries[[1,6],[6,1],[2,7],[2,6]]
expected[1,0,1,0]
checking account