3. Disjoint Sets The uptrees used to represent sets in the union-find algorithm can be stored in two n-element arrays. Tbe up array stores the parent of each node (or -1 if the node has no parenf). The weight array stores the number of items in a set (its weight) if the node is the root (representative node) of a set. (If a node is not a root the contents of its location in the weight array are umdefined-we don't care what value it holds, it can be zero or any other mmber.) The following shows a collection ofsets containing the mumbers 1 through 14, without the weight array filled in: 10 11 12 13 14 10 1 1-185513 5 22 weight a) b) Draw a picture of the uptrees represented by the data in the up Now, draw a new set of uptrees to show the results of executing, array shown above. union(find (1), find (11)): find (9) Regardless of how the trees from part a) were constructed, here assume that find uses path compression and that union uses union-by-size (aka union by weight). In case of ties in size, always make the higher numbered root point to the lower mmbered one. Unioning a set with itself does nothing. c) Update the up and weight arrays at the top of the previous page to reflect the picture after array and update the contents of the up part b). That is, fill in the contents ofthe weight array d) What is the worst case big-O running time of a single find operation if mion by size (aka union by weight) and path compression are used (assuming you are always passed roots as parameters? N = total # of elements in all sets. (no esplanation required) e) Assuming that you are using union by size and path conmpression, how long would we expect a sequence ofN-1 union operations and J find operations to take? (N = total # of elements in all sets) Express your answer in terms of big-0. (no esplanation required)