A node v in a directed rooted tree T = (V, E) is an ancestor of node u if the path from the root to u

passes through v. The lowest common ancestor(LCA) of two nodes u and v in T is the deepest node

w that is an ancestor of both u and v, where the depth of node is defined as the number of edges on

the path from the root to that node. Given two nodes u and v in an directed rooted tree T, design

an algorithm that finds the lowest common ancestor in O(h) time, where h is the distance between

u and v in the underlying undirected version of T. You are allowed to do O(jEj) preprocessing on

the tree before various pairs u and v are given to you, and the cost of preprocessing will not be

counted in your LCA algorithm.

1. A node v in a directed rooted tree T = (V, E) is an ancestor of node if the path from the root to u passes through v. The lowest common ancestor(LCA) of two nodes u and v in T is the deepest node w that is an ancestor of both u and v, where the depth of node is defined as the number of edges on the path from the root to that node. Given two nodes u and v in an directed rooted tree T, design an algorithm that finds the lowest common ancestor in O(h) time, where h is the distance between u and v in the underlying undirected version of T. You are allowed to do O(IEl) preprocessing on the tree before various pairs u and v are given to you, and the cost of preprocessing will not be counted in your LCA algorithm