1import java.util.*;
2
3public class Solution {
4    static ArrayList<Integer>[] adjList;
5    static boolean[] visited;
6
7    private static int dfs(int node, int seats, long[] cost) {
8        visited[node] = true;
9        int representatives = 1;
10        for (int neighbor : adjList[node]) {
11            if (!visited[neighbor]) {
12                int reps = dfs(neighbor, seats, cost);
13                cost[0] += (reps + seats - 1) / seats;
14                representatives += reps;
15            }
16        }
17        return representatives;
18    }
19
20    public static long minimumFuelCost(int[][] roads, int seats) {
21        int n = roads.length + 1;
22        adjList = new ArrayList[n];
23        visited = new boolean[n];
24        for (int i = 0; i < n; i++) {
25            adjList[i] = new ArrayList<>();
26        }
27        for (int[] road : roads) {
28            adjList[road[0]].add(road[1]);
29            adjList[road[1]].add(road[0]);
30        }
31        long[] cost = new long[1];
32        dfs(0, seats, cost);
33        return cost[0];
34    }
35
36    public static void main(String[] args) {
37        int[][] roads = {{3,1},{3,2},{1,0},{0,4},{0,5},{4,6}};
38        int seats = 2;
39        System.out.println(minimumFuelCost(roads, seats));
40    }
41}

1using System.Collections.Generic;

class Solution {
    public static long MinimumFuelCost(int[][] roads, int seats) {
        int n = roads.Length + 1;
        List<int>[] adjList = new List<int>[n];
        for (int i = 0; i < n; ++i) adjList[i] = new List<int>();
        foreach (var road in roads) {
            adjList[road[0]].Add(road[1]);
            adjList[road[1]].Add(road[0]);
        }

        bool[] visited = new bool[n];
        Queue<(int node, int reps)> q = new Queue<(int, int)>();
        q.Enqueue((0, 0));
        visited[0] = true;
        long cost = 0;

        while (q.Count > 0) {
            var (node, reps) = q.Dequeue();
            int max_reps = reps + 1;
            long nodeFuel = (max_reps + seats - 1) / seats;
            cost += nodeFuel;
            foreach (int neighbor in adjList[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.Enqueue((neighbor, max_reps));
                }
            }
        }

        return cost;
    }

    static void Main() {
        int[][] roads = { new int[]{0,1}, new int[]{0,2}, new int[]{0,3} };
        int seats = 5;
        Console.WriteLine(MinimumFuelCost(roads, seats));
    }
}