class Solution {
public:
    int dfs(int root,vector<vector<int>>& g,vector<int>& vis,vector<int>& nodeCount,long long& ans,int& seats){
        vis[root] = 1;
        for(auto i:g[root]){
            if(vis[i] != 1)nodeCount[root] += dfs(i,g,vis,nodeCount,ans,seats);
        }
        if(root!=0){
            ans += nodeCount[root]/seats;
            if(nodeCount[root] % seats) ans+=1;
        }
        return nodeCount[root];
    }
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        long long ans = 0;
        int n = roads.size() + 1;
        vector<vector<int>> g(n);
        vector<int> vis(n,-1);
        vector<int> nodeCount(n,1);
        for(auto r:roads){
            g[r[0]].push_back(r[1]);
            g[r[1]].push_back(r[0]);
        }
        dfs(0,g,vis,nodeCount,ans,seats);
        return ans;
    }
};