Museum Isolation Wing
Minimum vertex and boundary-edge cost for k connected nodes in a tree
A museum's rooms are connected by doors. The room-and-door network is a tree: every pair of rooms has exactly one route between them.
The museum must select exactly k rooms to form a temporary isolation wing. The selected rooms must be connected using only selected rooms. Every door with exactly one selected endpoint must be sealed; doors with both endpoints selected or both endpoints unselected require no work.
fees[i] is the preparation fee for selecting room i. A negative fee represents a credit. Each entry [u, v, cost] in doors describes a door between rooms u and v and its sealing cost.
The total cost is the sum of the preparation fees of selected rooms plus the sealing costs of all doors with exactly one selected endpoint.
Return the minimum possible total cost. The isolation wing may be located anywhere in the museum, and its total cost may be negative.
Examples
Example 1
Input: fees = [6,-5,2,4], doors = [[0,1,3],[1,2,8],[1,3,1]], k = 2 Output: 1
Select rooms 1 and 2. Their connecting door stays open, while the doors from room 1 to rooms 0 and 3 must be sealed. This choice is cheaper than either other connected pair.
Example 2
Input: fees = [4,-9,3], doors = [[0,1,10],[1,2,20]], k = 3 Output: -2
Every room must be selected, so no door is sealed. All room preparation fees, including the credit, contribute to the cost.
Example 3
Input: fees = [8,-10,8], doors = [[0,1,2],[1,2,2]], k = 1 Output: -6
Only one room is selected. Selecting room 1 combines its preparation credit with the sealing costs of both incident doors.
Constraints
- 1 <= len(fees) <= 2000
- 1 <= k <= min(40, len(fees))
- -1000000 <= fees[i] <= 1000000
- doors contains exactly len(fees) - 1 entries.
- Each door is [u, v, cost], where 0 <= u, v < len(fees), u != v, and 0 <= cost <= 1000000.
- The doors form a connected, undirected tree.
An iterative traversal avoids recursion-depth problems on a long chain. The intended solution uses O(n * k^2) time and O(n * k) space, where n is the number of rooms.
Hints
Show hint 1Hint 1
Root the tree anywhere. Every connected selection has a unique selected room closest to the root.
Show hint 2Hint 2
For each room, track the minimum cost of a connected selection of each possible size that contains that room and stays inside its subtree. When processing a child, either seal its connecting door or merge a connected selection containing that child.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you reconstruct one optimal set of room indices?
- How would the dynamic program change if a specified room had to belong to the isolation wing?
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