# 2477. Minimum Fuel Cost to Report to the Capital
###### tags: `Leetcode` `Medium` `DFS` `Tree`
Link: https://leetcode.com/problems/minimum-fuel-cost-to-report-to-the-capital/description/
## 思路
和[2467. Most Profitable Path in a Tree](https://hackmd.io/wgTl8LzpQTCJ1siUYKtUHw)方法差不多
参考[这里](https://leetcode.com/problems/minimum-fuel-cost-to-report-to-the-capital/solutions/2831676/c-java-python3-simple-dfs-o-n/)

DFS
- Imagine you are at a leaf node, you move towards 0. There will be only 1 person in the car (you)
- Now let's say you're somewhere in the middle of the tree, with a car of size 5. You have 3 children nodes. Let's say each child node brings 1 car of 3 people. So a total of 3 * 3 = 9 people. Including you there are 10 people now. Now you have 3 cars from the child nodes and one car of your own. You actually need just 10 / 5 = 2 cars. You take 2 cars and move towards 0
## Code

class Solution {
    long ans = 0;
    public long minimumFuelCost(int[][] roads, int seats) {
        List<List<Integer>> graph = new ArrayList<>();
        int n = roads.length+1;
        for(int i=0; i<n; i++) graph.add(new ArrayList<>());
        for(int[] road:roads){
            graph.get(road[0]).add(road[1]);
            graph.get(road[1]).add(road[0]);
        }
        dfs(0, 0, seats, graph);
        return ans;
    }
    public int dfs(int cur, int prev, int seats, List<List<Integer>> graph){
        int people = 1;
        for(int next:graph.get(cur)){
            if(next==prev) continue;
            people += dfs(next, cur, seats, graph);
        }
        if(cur!=0) ans += (people+seats-1)/seats;
        return people;
    }
}