2.) Vacation Planning. You're a travel agent trying to plan out which destinations to include in your next vacation package. You have a list of the n potential destinations and their "scores", S = [81, 82, , Sn], numbers that indicate how desirable each destination is. However, there's a catch: certain destinations are "too close together", and you can't include any two destinations that are too close, since then the scenery will be too similar. In fact, the destinations form a tree, where each destination is a vertex, and the edges correspond to destinations being too close. We want to determine the maximum possible "vacation score" (the sum of the scores of destinations chosen) subject to this constraint. You may assume you're given access to a function children(x) which returns a list of all the child vertices of destination x. You can call children() as many times as you want (i.e., assume it runs in O(1) time). The tree is always rooted at destination 1. For example, suppose our destinations form the tree on the right, and we have S = [10,6,5,2,7,4,11]. Choosing destination 1 would mean we couldn't choose destination 2 or 4, since there are edges between destinations 1 and 2 and between 1 and 4. Likewise, choosing destination 6 would prevent us from choos- ing 2 or 7. children (1) would return [2,4], children (2) would return [3, 5, 6], children(6) would return [7], and all other children() calls would return the empty list. Here, the maximum possible vacation score is 33, which we can get by choosing destinations 1, 3, 5, and 7, for scores of 10+5+7+11=33. Design a dynamic programming algorithm to efficiently solve this problem. a.) Define the entries of your table in words, e.g. T[i] or T[i, j] is ... b.) State your base cases and the recurrence for entries of your table in terms of smaller sub- problems. Briefly explain in words why it is correct. c.) Analyze the running time of your algorithm. Note: For this question, you do not need to consider the running time of anything other than filling out your table (i.e. you can assume you're given an ordering of the nodes in the tree "for free" if you need it)