2477. Minimum Fuel Cost to Report to the Capital - Explanation

class Solution:
    def minimumFuelCost(self, roads: list[list[int]], seats: int) -> int:
        adj = defaultdict(list)
        for src, dst in roads:
            adj[src].append(dst)
            adj[dst].append(src)

        res = 0
        def dfs(node, parent):
            nonlocal res
            passengers = 0
            for child in adj[node]:
                if child != parent:
                    p = dfs(child, node)
                    passengers += p
                    res += ceil(p / seats)
            return passengers + 1

        dfs(0, -1)
        return res

class Solution:
    def minimumFuelCost(self, roads: list[list[int]], seats: int) -> int:
        n = len(roads) + 1
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        passengers = [1] * n
        res = 0

        for src, dst in roads:
            adj[src].append(dst)
            adj[dst].append(src)
            indegree[src] += 1
            indegree[dst] += 1

        q = deque()
        for i in range(1, n):
            if indegree[i] == 1:
                q.append(i)

        while q:
            node = q.popleft()
            res += math.ceil(passengers[node] / seats)
            for parent in adj[node]:
                indegree[parent] -= 1
                if indegree[parent] == 1 and parent != 0:
                    q.append(parent)
                passengers[parent] += passengers[node]

        return res