Tree DP

Questions 1 to 5 of 6

1. 1. A node is not chosen. Why does its without value add the larger of with and without for each child?

   Its children must be chosen whenever the parent is not, so each child contributes its with valueEach child's with value is always larger than its without value, so the code can skip the comparisonIts children are free to be chosen or not, so each child contributes whichever of its two values is largerThe parent's with value needs both children's larger values, so the same values are reused
2. 2. The tree below has weights 5 at the root, 1 on the left, 6 on the right, and 2 under the 1. Which set of nodes gives the best total? ``text 5 / \ 1 6 / 2 ``

   Nodes 5 and 6, total 11Nodes 2 and 6, total 8Nodes 1 and 6, total 7Nodes 5 and 1, total 6
3. 3. This program runs the tree DP on a small tree. ``cpp #include <algorithm> #include <iostream> #include <memory> #include <utility> struct Node { long long value; std::unique_ptr<Node> left; std::unique_ptr<Node> right; }; std::unique_ptr<Node> make(long long value, std::unique_ptr<Node> left = nullptr, std::unique_ptr<Node> right = nullptr) { auto node = std::make_unique<Node>(); node->value = value; node->left = std::move(left); node->right = std::move(right); return node; } struct Best { long long with; // best total when this node is chosen long long without; // best total when this node is not chosen }; Best solve(const Node* n) { if (!n) return {0, 0}; Best l = solve(n->left.get()); Best r = solve(n->right.get()); return {n->value + l.without + r.without, std::max(l.with, l.without) + std::max(r.with, r.without)}; } int main() { auto root = make(4, make(9, make(1)), make(2, nullptr, make(6))); Best b = solve(root.get()); std::cout << "best: " << std::max(b.with, b.without) << '\n'; } `` What does it print?

   best: 11best: 12best: 22best: 15
4. 4. This program prints the root's with value as the answer, and also prints the correct answer. ``cpp #include <algorithm> #include <iostream> #include <memory> #include <utility> struct Node { long long value; std::unique_ptr<Node> left; std::unique_ptr<Node> right; }; std::unique_ptr<Node> make(long long value, std::unique_ptr<Node> left = nullptr, std::unique_ptr<Node> right = nullptr) { auto node = std::make_unique<Node>(); node->value = value; node->left = std::move(left); node->right = std::move(right); return node; } struct Best { long long with; // best total when this node is chosen long long without; // best total when this node is not chosen }; Best solve(const Node* n) { if (!n) return {0, 0}; Best l = solve(n->left.get()); Best r = solve(n->right.get()); return {n->value + l.without + r.without, std::max(l.with, l.without) + std::max(r.with, r.without)}; } int main() { auto root = make(1, make(8, make(5)), make(9)); Best s = solve(root.get()); std::cout << "buggy: " << s.with << " correct: " << std::max(s.with, s.without) << '\n'; } `` What does it print?

   buggy: 6 correct: 17buggy: 17 correct: 17buggy: 8 correct: 17buggy: 6 correct: 6
5. 5. Which statements about the tree DP method in this lesson are true? Pick all that apply.

   Pick every answer that is true.

   The answer for the whole tree is the larger of the root's with and without valuesA missing child contributes {0, 0} to its parent's numberswith for a node uses the children's with valuesThe chosen set may be empty, so no node has to be forced into the answerAdding every node's weight gives the right answer for the first example tree