<p>There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of <code>n</code> cities numbered from <code>0</code> to <code>n - 1</code> and exactly <code>n - 1</code> roads. The capital city is city <code>0</code>. You are given a 2D integer array <code>roads</code> where <code>roads[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> denotes that there exists a <strong>bidirectional road</strong> connecting cities <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code>.</p>

<p>There is a meeting for the representatives of each city. The meeting is in the capital city.</p>

<p>There is a car in each city. You are given an integer <code>seats</code> that indicates the number of seats in each car.</p>

<p>A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.</p>

<p>Return <em>the minimum number of liters of fuel to reach the capital city</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/22/a4c380025e3ff0c379525e96a7d63a3.png" style="width: 303px; height: 332px;" />
<pre>
<strong>Input:</strong> roads = [[0,1],[0,2],[0,3]], seats = 5
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
- Representative<sub>1</sub> goes directly to the capital with 1 liter of fuel.
- Representative<sub>2</sub> goes directly to the capital with 1 liter of fuel.
- Representative<sub>3</sub> goes directly to the capital with 1 liter of fuel.
It costs 3 liters of fuel at minimum. 
It can be proven that 3 is the minimum number of liters of fuel needed.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/11/16/2.png" style="width: 274px; height: 340px;" />
<pre>
<strong>Input:</strong> roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
<strong>Output:</strong> 7
<strong>Explanation:</strong> 
- Representative<sub>2</sub> goes directly to city 3 with 1 liter of fuel.
- Representative<sub>2</sub> and representative<sub>3</sub> go together to city 1 with 1 liter of fuel.
- Representative<sub>2</sub> and representative<sub>3</sub> go together to the capital with 1 liter of fuel.
- Representative<sub>1</sub> goes directly to the capital with 1 liter of fuel.
- Representative<sub>5</sub> goes directly to the capital with 1 liter of fuel.
- Representative<sub>6</sub> goes directly to city 4 with 1 liter of fuel.
- Representative<sub>4</sub> and representative<sub>6</sub> go together to the capital with 1 liter of fuel.
It costs 7 liters of fuel at minimum. 
It can be proven that 7 is the minimum number of liters of fuel needed.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/27/efcf7f7be6830b8763639cfd01b690a.png" style="width: 108px; height: 86px;" />
<pre>
<strong>Input:</strong> roads = [], seats = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> No representatives need to travel to the capital city.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>roads.length == n - 1</code></li>
	<li><code>roads[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li><code>roads</code> represents a valid tree.</li>
	<li><code>1 &lt;= seats &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        # simulate driving from outside to center using bfs. The starting nodes
        # are the leaves (nodes with 1 edge), Since these nodes cannot be picked up,
        # we can start a car here. Each item in the queue needs to have the current city
        # and the number of free seats in the car. We need a seen list so we never move
        # backwards (why go back 1 and forward when to pick someone up when they can
        # move forward in 1 spot). Always pick someone up if possible, if not a new starts
        # driving. Could make a new car by adding a new item to queue, but if seats is 
        # small and distance from leaf to capital is large lots of repeated work. ex:
        # in Example 2, imagine seats is 1. Someone at city 2, queue has (2, 0)
        # to represent car at city 2 with 0 available seats. Then at city 3 we have to 
        # make a new car, queue has (3, 0), (3, 0). A third car is made at 1. 
        # Essentially, a small seat value makes it so lots of cars are made (up to n).
        # Instead, we could use a 3-tuple, where values are as such (location, open
        # seats, number of cars). If we have no open seats at a city, we incremenet
        # the number of cars and reset number of open seats. Then only 1 tuple made for
        # the path from 2 -> 0 in Example 2. Each time we move to a new city, the 
        # number of liters is incrememented by the number of cars that traveled to that
        # city

        import math

        # number of edges connected to a city
        degrees = defaultdict(int)
        graph = defaultdict(list)
        for city1, city2 in roads:
            city1_edges = graph[city1]
            city1_edges.append(city2)
            graph[city1] = city1_edges

            city2_edges = graph[city2]
            city2_edges.append(city1)
            graph[city2] = city2_edges

            degrees[city1] = degrees[city1] + 1
            degrees[city2] = degrees[city2] + 1
        
        dq = deque()
        num_people = defaultdict(int)
        for city, degree in degrees.items():
            num_people[city] = 1

            if degree == 1:
                # start at leaf cities
                dq.append(city)

        liters = 0
        seen = set()
        

        while len(dq) > 0:
            # each time we visit a city, all representatives on the outside (from leaves)
            # has already made it to the current city. Check how many people there are,
            # that is how many cars we need to travel to the next city and also how many
            # liters of fuel we spend to do so
            city = dq.popleft()

            if city == 0:
                continue
            
            seen.add(city)

            people_at_curr = num_people[city]
            cars_needed = math.ceil(people_at_curr / seats)

            # add cost of driving to next city
            liters += cars_needed
            
            # get next city to drive to
            next_city = None
            for neighbor in graph[city]:
                if neighbor in seen:
                    continue
                else:
                    next_city = neighbor
                    break
            
            # add number of representatives that will meet at next city
            num_people[next_city] = num_people[next_city] + people_at_curr
            # degree of next city decreases, if it is now 1 (not waiting on anyone
            # to travel to capital) it can be added to the queue
            degrees[next_city] = degrees[next_city] - 1
            if degrees[next_city] == 1:
                dq.append(next_city)



        return liters

1640