1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define MAX_CITIES 100000
6
7// Adjacency list
8int tree[MAX_CITIES][MAX_CITIES];
9int child_count[MAX_CITIES];
10int visited[MAX_CITIES];
11
12int dfs(int node, int seats) {
13    visited[node] = 1;
14    int totalFuel = 0;
15    for (int i = 0; i < child_count[node]; ++i) {
16        int next = tree[node][i];
17        if (!visited[next]) {
18            int people = dfs(next, seats);
19            totalFuel += (people + seats - 1) / seats;
20            totalFuel += people; // Adding people to fuel calculation
21        }
22    }
23    return totalFuel + 1;
24}
25
26int minimumFuelCost(int roads[][2], int roadsSize, int seats) {
27    for (int i = 0; i < roadsSize; ++i) {
28        int a = roads[i][0];
29        int b = roads[i][1];
30        tree[a][child_count[a]++] = b;
31        tree[b][child_count[b]++] = a;
32    }
33    return dfs(0, seats) - 1; // Subtract 1 as node 0 doesn't use fuel
34}
35
36int main() {
37    int roads[5][2] = {{3,1},{3,2},{1,0},{0,4},{0,5},{4,6}};
38    int seats = 2;
39    printf("%d\n", minimumFuelCost(roads, 5, seats));
40    return 0;
41}

1