1using System;
2using System.Collections.Generic;
3
4class Solution {
5    static List<int>[] adjList;
6    static bool[] visited;
7
8    static int Dfs(int node, int seats, ref long cost) {
9        visited[node] = true;
10        int representatives = 1;
11        foreach (int neighbor in adjList[node]) {
12            if (!visited[neighbor]) {
13                int reps = Dfs(neighbor, seats, ref cost);
14                cost += (reps + seats - 1) / seats;
15                representatives += reps;
16            }
17        }
18        return representatives;
19    }
20
21    public static long MinimumFuelCost(int[][] roads, int seats) {
22        int n = roads.Length + 1;
23        adjList = new List<int>[n];
24        visited = new bool[n];
25        for (int i = 0; i < n; ++i) adjList[i] = new List<int>();
26        foreach (var road in roads) {
27            adjList[road[0]].Add(road[1]);
28            adjList[road[1]].Add(road[0]);
29        }
30        long cost = 0;
31        Dfs(0, seats, ref cost);
32        return cost;
33    }
34
35    static void Main(string[] args) {
36        int[][] roads = new int[][] { new int[]{ 3,1}, new int[]{ 3,2}, new int[]{ 1,0}, new int[]{ 0,4}, new int[]{ 0,5}, new int[]{ 4,6}};
37        int seats = 2;
38        Console.WriteLine(MinimumFuelCost(roads, seats));
39    }
40}

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));
    }
}