rust 解法, 执行用时: 48 ms, 内存消耗: 22.2 MB, 提交时间: 2023-12-05 07:50:14

impl Solution {
    pub fn minimum_fuel_cost(roads: Vec<Vec<i32>>, seats: i32) -> i64 {
        let mut g = vec![vec![]; roads.len() + 1];
        for e in &roads {
            let x = e[0] as usize;
            let y = e[1] as usize;
            g[x].push(y); // 记录每个点的邻居
            g[y].push(x);
        }
        let mut ans = 0i64;
        Self::dfs(0, 0, &g, seats, &mut ans);
        ans
    }

    fn dfs(x: usize, fa: usize, g: &Vec<Vec<usize>>, seats: i32, ans: &mut i64) -> i32 {
        let mut size = 1;
        for &y in &g[x] {
            if y != fa { // 递归子节点，不能递归父节点
                size += Self::dfs(y, x, g, seats, ans); // 统计子树大小
            }
        }
        if x != 0 { // x 不是根节点
            *ans += ((size - 1) / seats + 1) as i64; // ceil(size/seats)
        }
        size
    }
}

javascript 解法, 执行用时: 424 ms, 内存消耗: 96.4 MB, 提交时间: 2023-12-05 07:49:46

/**
 * @param {number[][]} roads
 * @param {number} seats
 * @return {number}
 */
var minimumFuelCost = function (roads, seats) {
    const g = Array(roads.length + 1).fill(null).map(() => []);
    for (const [x, y] of roads) {
        g[x].push(y); // 记录每个点的邻居
        g[y].push(x);
    }

    let ans = 0;
    function dfs(x, fa) {
        let size = 1;
        for (const y of g[x]) {
            if (y !== fa) { // 递归子节点，不能递归父节点
                size += dfs(y, x); // 统计子树大小
            }
        }
        if (x !== 0) { // x 不是根节点
            ans += Math.ceil(size / seats);
        }
        return size;
    }
    dfs(0, -1);
    return ans;
};

cpp 解法, 执行用时: 584 ms, 内存消耗: 199.8 MB, 提交时间: 2023-08-22 09:34:27

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        // 建图
        vector<int> e[n];
        for (auto &road : roads) {
            e[road[0]].push_back(road[1]);
            e[road[1]].push_back(road[0]);
        }

        long long ans = 0;
        // DFS 统计子树大小，同时统计答案
        function<int(int, int)> dfs = [&](int sn, int fa) {
            int ret = 1;
            for (int fn : e[sn]) if (fn != fa) {
                // 计算 sn -> fn 这条边的贡献
                int t = dfs(fn, sn);
                ans += (t + seats - 1) / seats;
                // 更新子树大小
                ret += t;
            }
            return ret;
        };
        dfs(0, -1);
        return ans;
    }
};

java 解法, 执行用时: 41 ms, 内存消耗: 83.1 MB, 提交时间: 2023-08-22 09:32:38

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

cpp 解法, 执行用时: 496 ms, 内存消耗: 207.5 MB, 提交时间: 2023-08-22 09:32:14

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        vector<vector<int>> g(n);
        for(auto& v : roads){
            int f = v[0], t = v[1];
            g[f].emplace_back(t);
            g[t].emplace_back(f);
        }
        long long ans = 0;
        function<int(int, int)> dfs = [&](int o, int p)-> int {
            int size = 1;
            for(auto i : g[o]){
                if(i == p) continue;
                size += dfs(i, o);
            }
            if(o != 0) ans += (size + seats - 1) / seats;
            return size;
        };
        dfs(0, -1);
        return ans;
    }    
};

golang 解法, 执行用时: 276 ms, 内存消耗: 45.6 MB, 提交时间: 2023-08-22 09:31:48

func minimumFuelCost(roads [][]int, seats int) int64 {
	ans := 0
	g := make([][]int, len(roads)+1)
	for _, e := range roads {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}
	var dfs func(int, int) int
	dfs = func(x, fa int) int {
		size := 1
		for _, y := range g[x] {
			if y != fa {
				size += dfs(y, x)
			}
		}
		if x > 0 {
			ans += (size + seats - 1) / seats
		}
		return size
	}
	dfs(0, -1)
	return int64(ans)
}

python3 解法, 执行用时: 404 ms, 内存消耗: 157.3 MB, 提交时间: 2023-08-22 09:30:41

'''
考虑每条边上至少需要多少辆车。
以 0 为根，设子树 x 的大小为 size，那么它到它父节点这条边的「流量」是 size，
那么就至少需要 size/seats 辆车。
累加除了 x=0 以外的值，就是答案。
'''
class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        ans = 0
        g = [[] for _ in range(len(roads) + 1)]
        for x, y in roads:
            g[x].append(y)
            g[y].append(x)
        def dfs(x: int, fa: int) -> int:
            size = 1
            for y in g[x]:
                if y != fa:
                    size += dfs(y, x)
            if x:
                nonlocal ans
                ans += (size + seats - 1) // seats
            return size
        dfs(0, -1)
        return ans