573. Collecting Every Apple and Coming Back
Some nodes of a tree hold an apple. Start at node 1, walk along edges, collect every apple, and return to node 1. Each traversal of an edge takes one second, in either direction. Print the fewest seconds needed.
4 nodes, apples at 2 and 4, edges 1-2 1-3 3-4 -> 6
3 nodes, apple only at node 1 -> 0 you are already there
## Every used edge is used exactly twice
The walk starts and ends at node 1. Removing an edge splits the tree in two, so any walk that crosses it must cross back, and the number of crossings is even.
And no edge ever needs more than two crossings: go down into a subtree once, take everything wanted from it, come back. So the answer is
2 * (the number of edges that must be used at all)
which reduces the whole problem to deciding WHICH edges are used.
## The rule for one edge
The edge from u to its parent is worth entering exactly when u's subtree contains an apple.
If it holds none, going down is pure waste; if it holds even one, that apple cannot be reached
any other way, because a tree has exactly one path between two nodes.
So define
keep[u] = true if u's subtree contains at least one apple
and the answer counts 2 for every non-root u with keep[u] true.
## Writing it as a children-first sweep
cost[u] = sum over children c with keep[c] of (cost[c] + 2)
keep[u] = apple[u] or any keep[c]
The answer is cost[1]. The + 2 pays for the edge down to c and back.
## The base case is where this lives
A leaf has cost = 0 and keep = apple[leaf]. Everything else follows from propagating that
one fact upwards, which is why this problem is the topic's clearest example of a base case
doing the real work.
## Two cases to get right
An apple at the ROOT costs nothing: you begin standing on it, and cost[1] never charges for
the root itself.
A tree with no apples at all answers 0. Both cases are in the tests, and a solution that charges for the root or assumes at least one apple fails them.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - each flag is `0` or `1` - the input is always a tree
Input
The first line contains an integer n, the number of nodes.
The second line contains n integers, each 0 or 1, where the ith is 1
when node i holds an apple.
Each of the next n - 1 lines contains two integers u and v, an edge of
the tree. Nodes are numbered 1 to n and the walk starts at node 1.
Output
Print one integer, the fewest seconds needed to collect every apple and return to node 1.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.