Recipe Reminder Stations
Minimum cost to cover every tree node using radius-two node coverage
A recipe app organizes preparation steps as a rooted tree. Each node represents one step, and an edge connects a step to its immediate prerequisite.
The tree is described by parents: node 0 is the root, with parents[0] = -1, and every other node i has parent parents[i]. Edges can be traversed in either direction.
You may place a reminder station at any node i, paying costs[i]. A station covers its own node and every node whose tree distance from it is at most two edges. Stations have no capacity limit, and their coverage may overlap.
Return the minimum total cost of placing stations so that every node is covered.
Examples
Example 1
Input: parents = [-1,0,1,2,3,4], costs = [9,8,1,8,8,2] Output: 3
The steps form a six-node chain. A station at node 2 reaches nodes 0 through 4, but cannot reach node 5, so additional coverage is needed.
Example 2
Input: parents = [-1,0,0,0,0], costs = [20,7,3,8,6] Output: 3
Every nonroot step is directly attached to the root. A station at any leaf can reach all other leaves through the root, so one station can cover the entire tree.
Example 3
Input: parents = [-1], costs = [0] Output: 0
The only step must be covered. Placing a station there is free.
Constraints
- 1 <= parents.length <= 4000
- costs.length == parents.length
- parents[0] == -1
- 0 <= parents[i] < i for every i > 0
- 0 <= costs[i] <= 1000000
The reference solutions use O(n) time and O(n) space, with a constant number of states per node. A state records the nearest selected node at distance 0, 1, 2, or at least 3, and the farthest uncovered node at distance -1, 0, or 1; -1 means everything is covered. An uncovered node at distance 2 cannot be rescued from outside the completed subtree.
Hints
Show hint 1Hint 1
Process subtrees from the leaves upward. A subtree can leave some nodes uncovered only if a station outside that subtree could still reach them.
Show hint 2Hint 2
For each subtree, track the nearest station's distance from its root and the farthest still-uncovered node's distance. Cap irrelevant station distances, and test whether stations in one merged part cover the outstanding nodes in the other.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you extend the state representation if every station covered nodes within a supplied radius r?
- How would you reconstruct an optimal set of station indices, breaking ties by the lexicographically smallest increasing list?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem