You are given a complete binary tree of height h with n = 2^h leaves, where each node x (internal nodes and leaves) of the tree has an associated value v(x) (which is an arbitrary real number). If x is a leaf, we denote by A(x), the set of ancestors of x (including x as one of its own ancestors). That is, A(x) contains x, xs parent, xs grandparent, etc. up to the root of the tree. Similarly, if x and y are distinct leaves, we denote A(x, y) as the ancestors of either x or y. That is A(x, y) = A(x) A(y). We define a function f(x, y) as the sum of all values of the nodes in A(x, y). An example is shown in Figure 1. We will generate an efficient algorithm that efficiently finds two leaves x0 and y0 such that f(x0, y0) is as large as possible (largest among all the pairs of leaves). Try to give a solution with O(n) running time. For partial credit, you may provide an algorithm with O(n lg n) running time. Hint: In order to get the running time O(n) you should think about how you can strengthen the recursion that is, return more information from the recursive subproblems