Suppose we are given a set of points P = {P1 , P2 , , Pn }, together with a distance function d on the set P ; d is simply a function on pairs of

, Pn }, together with a distance function d on the setP ; d is simply a function on pairs of points in P with the properties that d(pi , pj ) = d(pj , Pi ) > 0 iff i = j,and that d(pi , pi ) = 0 for each i.We define a hierarchical metric on P to be any distance function that can be constructed as follows:We build a rooted tree T with n leaves, and we associate with each node v of T (both leaves and internalnodes) a height h(v). These heights must satisfy the properties that h(v) = 0 for each leaf v, and if u is theparent of v in T , then h(u) h(v). We place each point in P at a distinct leaf in T .Now, for any pair of points pi and pj , their distance (pi , pj ) is defined as follows: We determine thelowest common ancestor v in T of the leaves containing pi and pj , and define (pi , pj ) = h(v).We say that a hierarchical metric is consistent with our distance function d if, for all pairs i, j, we have (pi , pj ) d(pi , pj ).Give a polynomial-time algorithm that takes the distance function d and produces a hierarchical metric with the following properties.1. is consistent with d, and(pi , pj ) for each pair of pointspi and pj