Suppose that you are given a binary tree T with vertices V and edges E$,$

in adjacency list format. Assume that there is a designated root node x$.$ For

two nodes u$,$ v in V $,$ u is an ancestor of v if the path from the root x to v

passes through u$.$ If u is an ancestor of v$,$ then v is said to be a descendant

of u$.$

Propose an algorithm to preprocess the tree so that questions of the type $$Is u an ancestor

of v$?$ can be answered in constant time. The preprocessing should take

linear time. $($To $$preprocess$$ the tree means to construct a new representation of the tree, or a new representation of some properties associated with

the tree, so that that representation can then be used to answer questions

of the given form. This new representation can be an array, a tree, an integer, a graph, or any other object that meets the requirements.$).$ Hint: DFS$.$