Tree DP

Questions 1 to 5 of 6

1. 1. A node has weight 10. Its left child has take 3 and skip 7. Its right child has take 9 and skip 4. What is the take value of the node?

   16212226
2. 2. A version that keeps one number per node returns 16 for the path 5 - 10 - 1, where 5 is the root, 10 is its child and 1 is the grandchild. Which group does that 16 come from?

   {5, 1}, which is allowed and totals 6{10}, which is allowed and totals 10{5, 10}, which is allowed and totals 15{5, 10, 1}, where 5 and 10 are joined and 10 and 1 are joined
3. 3. What does this program print? ``python from dataclasses import dataclass class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right @dataclass class Best: take: int skip: int def solve(node): if node is None: return Best(0, 0) left = solve(node.left) right = solve(node.right) take = node.value + left.skip + right.skip skip = max(left.take, left.skip) + max(right.take, right.skip) return Best(take, skip) # Tree P: 6 has children 2 (left) and -1 (right). # 2 has children 9 (left) and 1 (right). -1 has right child 5. p = TreeNode(6, TreeNode(2, TreeNode(9), TreeNode(1)), TreeNode(-1, None, TreeNode(5))) print(solve(p)) ``

   Best(take=21, skip=10)Best(take=22, skip=15)Best(take=21, skip=15)Best(take=15, skip=21)
4. 4. What does this program print? It uses the same TreeNode, Best and solve as the previous question, and max_weight_independent_set returns the bigger of the two values that solve gives for the root. ``python def max_weight_independent_set(root): best = solve(root) return max(best.take, best.skip) # Tree Q: 4 has children 7 (left) and -6 (right). # 7 has left child 3. -6 has right child 8. q = TreeNode(4, TreeNode(7, TreeNode(3), None), TreeNode(-6, None, TreeNode(8))) print(max_weight_independent_set(q)) ``

   1511819
5. 5. Which statements about the DP in this lesson are true?

   Pick every answer that is true.

   take of a node adds the skip values of its two childrentake of a node adds the take values of its two childrenA missing child returns take 0 and skip 0The answer for the whole tree is the take value of the rootThe time is O(n), because each node is visited once