2477. Minimum Fuel Cost to Report to the Capital

Medium
Description

有一棵以節點 0 為首都的樹，每條邊代表一條道路。每個非首都節點有一位代表需要前往首都。每輛車可載 seats 人，行駛一條邊消耗一單位燃油。代表可以在節點共乘。求所有代表到達首都的最小總燃油消耗。

Example:

Input: roads = [[0,1],[0,2],[0,3]], seats = 5 Output: 3

Intuition#

從葉子往根匯聚，每條邊需要的車輛數 = ceil(經過人數 / seats)。

  • 這是一棵樹，每個人最終都要到節點 0
  • 每條邊上通過的人數等於該邊子樹的節點數
  • 每條邊的燃油消耗 = ceil(通過人數 / seats)

Approaches#

⭐1: DFS（從根向下遞迴）#

  • 概念: DFS 計算每個子樹的節點數，每條邊的燃油消耗為 ceil(子樹人數 / seats)
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun minimumFuelCost(roads: Array<IntArray>, seats: Int): Long {
        val n = roads.size + 1
        val graph = Array(n) { mutableListOf<Int>() }
        for ((u, v) in roads) {
            graph[u].add(v)
            graph[v].add(u)
        }

        var fuel = 0L

        fun dfs(node: Int, parent: Int): Long {
            var people = 1L
            for (next in graph[node]) {
                if (next != parent) {
                    people += dfs(next, node)
                }
            }
            if (node != 0) {
                fuel += (people + seats - 1) / seats
            }
            return people
        }

        dfs(0, -1)
        return fuel
    }
}

2: BFS（拓撲排序從葉子到根）#

  • 概念: 從葉子節點開始 BFS，每次處理葉子時將人數傳遞給父節點
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun minimumFuelCost(roads: Array<IntArray>, seats: Int): Long {
        val n = roads.size + 1
        if (n == 1) return 0

        val graph = Array(n) { mutableListOf<Int>() }
        val degree = IntArray(n)
        for ((u, v) in roads) {
            graph[u].add(v)
            graph[v].add(u)
            degree[u]++
            degree[v]++
        }

        val queue = ArrayDeque<Int>()
        val people = LongArray(n) { 1L }
        for (i in 1 until n) {
            if (degree[i] == 1) queue.add(i)
        }

        var fuel = 0L
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            fuel += (people[node] + seats - 1) / seats
            for (next in graph[node]) {
                people[next] += people[node]
                degree[next]--
                if (degree[next] == 1 && next != 0) {
                    queue.add(next)
                }
            }
        }
        return fuel
    }
}

🔑 Takeaways#

  • Pattern: 樹上貪心 – 從葉子往根匯聚，每條邊獨立計算
  • 關鍵技巧: ceil(a / b) 在整數運算中用 (a + b - 1) / b；每條邊的燃油獨立計算，不需考慮共乘的路由