Problem 1-4. Sum your ancestors [30 points] You are given a complete binary tree of height h with n 2 leaves, where each node (internal nodes and leaves) of the tree has an associated value v (which is an arbitrary real number If r is a leaf, we denote by A(), the set of ancestors of r (including r as one of its own ancestors). That is, A( contains z, r's parent, r's grandparent, etc. up to the root of the tree. Similarly, if x and y are distinct leaves, we denote A(z, y) as the ancestors of either x or y. That is A(x,y)- A(r) U A(y). We define a function f(r, y) as the sum of all values of the nodes in A(r, y). An example is shown in Figure 1 Give a parallel algorithm that efficiently finds two leaves ro and yo such that f(ro, yo) is as large as possible (largest among all the pairs of leaves). Analyze the work and span of your algorithm. 30 10 36 12 15 10 7 9 16 19 27 13 Figure 1: A(r, y) is shown in bold. f(, y)- 19 +15 36+10+27+30 the value of f(r, y) is maximized for the leaves r andy 137. For this tree, Problem 1-4. Sum your ancestors [30 points] You are given a complete binary tree of height h with n 2 leaves, where each node (internal nodes and leaves) of the tree has an associated value v (which is an arbitrary real number If r is a leaf, we denote by A(), the set of ancestors of r (including r as one of its own ancestors). That is, A( contains z, r's parent, r's grandparent, etc. up to the root of the tree. Similarly, if x and y are distinct leaves, we denote A(z, y) as the ancestors of either x or y. That is A(x,y)- A(r) U A(y). We define a function f(r, y) as the sum of all values of the nodes in A(r, y). An example is shown in Figure 1 Give a parallel algorithm that efficiently finds two leaves ro and yo such that f(ro, yo) is as large as possible (largest among all the pairs of leaves). Analyze the work and span of your algorithm. 30 10 36 12 15 10 7 9 16 19 27 13 Figure 1: A(r, y) is shown in bold. f(, y)- 19 +15 36+10+27+30 the value of f(r, y) is maximized for the leaves r andy 137. For this tree