Description

• There are n nodes (numbered from 0 to n - 1) forming a tree, node 0 is the capital and other nodes are ordinary cities.
• Each ordinary city has 1 car, and a representative needs to be sent to the capital for the conference.
• Each car has seats seats, and 1 liter of gasoline is consumed for each edge passed.
• At each ordinary city, the representative can choose to sit in their own car or share a car with other representatives.
• Find the minimum amount of gasoline required in total.

Thought process

For each ordinary city (not the root node), reaching the root node through the parent is the shortest path. Therefore, the key to the problem is to use as few cars as possible.

Imagine that each representative first waits in their own city, and when all of its child node representatives arrive, seats are reassigned as much as possible to fill each car. Suppose there are K people gathering in city A, then at least $\lceil \frac{K}{\text{seats}} \rceil$ cars are needed to depart from A.parent. This is the greedy idea, and the reason it can be done is that when all child nodes continue to gather at A.parent, it is possible to carry all people by adding only A.parent’s car at most. Therefore, it is not a problem to abandon surplus cars in child nodes.

The appropriate algorithm for gathering from child nodes to root nodes is DFS.

Complexity

• Time complexity: O(n) for DFS.
• Space complexity: O(n) for the graph, since there are n-1 edges.

Code

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        n = len(roads) + 1
        # Note 1: Although it is a tree, storing it as a graph is more convenient
        # Mainly for distinguishing child and parent in DFS
        graph = [[] for _ in range(n)]
        for a, b in roads:
            graph[a].append(b)
            graph[b].append(a)

        res = 0

        def dfs(node, parent):
            people = 1
            for child in graph[node]:
                if child != parent:
                    people += dfs(child, node)
            # Note 2: After all people arrive at the capital, there is no 
            # need to travel further, so there is no need 
            # to add gasoline consumption
            if node != 0:
                nonlocal res
                res += (people + seats - 1) // seats
            return people

        dfs(0, -1)
        return res