Medium

题目描述

有一个树形（即连通的无向无环图）结构的国家网络，由编号从 0 到 n - 1 的 n 个城市和恰好 n - 1 条道路组成。首都是城市 0。给你一个二维整数数组 roads，其中 roads[i] = [ai, bi] 表示城市 ai 和 bi 之间存在一条双向道路。

每个城市的代表需要参加在首都举行的会议。

每个城市都有一辆汽车。给你一个整数 seats，表示每辆车的座位数。

代表可以使用自己城市的汽车出行，也可以换车与其他代表同行。两个城市之间的出行成本是一升燃料。

返回到达首都所需的最少燃料升数。

示例 1：

输入：roads = [[0,1],[0,2],[0,3]], seats = 5
输出：3
解释：
- 代表1直接到首都，消耗1升燃料。
- 代表2直接到首都，消耗1升燃料。
- 代表3直接到首都，消耗1升燃料。
最少需要3升燃料。可以证明3是所需的最少燃料升数。

示例 2：

输入：roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
输出：7
解释：
- 代表2直接到城市3，消耗1升燃料。
- 代表2和代表3一起到城市1，消耗1升燃料。
- 代表2和代表3一起到首都，消耗1升燃料。
- 代表1直接到首都，消耗1升燃料。
- 代表5直接到首都，消耗1升燃料。
- 代表6直接到城市4，消耗1升燃料。
- 代表4和代表6一起到首都，消耗1升燃料。
最少需要7升燃料。可以证明7是所需的最少燃料升数。

示例 3：

输入：roads = [], seats = 1
输出：0
解释：没有代表需要前往首都。

提示：

  • 1 <= n <= 10^5
  • roads.length == n - 1
  • roads[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • roads 表示一个有效的树
  • 1 <= seats <= 10^5

解题思路

这是一个树形动态规划问题。关键观察是，为了最小化燃料成本，我们应该让代表们尽可能拼车。

核心思路：

  1. 自底向上的思考：从叶子节点开始，每个子树内的代表最终都要通过根节点向上传递到首都。

  2. 拼车策略：对于任意节点，其子树中的所有代表都需要经过该节点前往父节点。如果有 people 个人需要通过某条边，那么需要的车辆数为 ⌈people/seats⌉。

  3. DFS后序遍历：使用深度优先搜索，在回溯过程中计算每个子树的人数和所需燃料。

算法步骤：

  • 构建邻接表表示树
  • 从首都（节点0）开始DFS遍历
  • 对于每个节点，先递归处理所有子节点
  • 计算当前子树的总人数（包括当前节点的代表）
  • 如果不是首都，计算从当前节点到父节点需要的车辆数和燃料
  • 返回子树的总人数供父节点使用

优化点：

  • 使用向上取整公式 (people + seats - 1) / seats 避免浮点运算
  • 首都节点无需向上传递，不计算燃料成本

代码实现

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        vector<vector<int>> graph(n);
        
        // 构建邻接表
        for (auto& road : roads) {
            graph[road[0]].push_back(road[1]);
            graph[road[1]].push_back(road[0]);
        }
        
        long long totalFuel = 0;
        
        function<int(int, int)> dfs = [&](int node, int parent) -> int {
            int people = 1; // 当前节点的代表
            
            // 遍历所有子节点
            for (int child : graph[node]) {
                if (child != parent) {
                    people += dfs(child, node);
                }
            }
            
            // 如果不是首都，计算到父节点的燃料成本
            if (node != 0) {
                totalFuel += (people + seats - 1) / seats;
            }
            
            return people;
        };
        
        dfs(0, -1);
        return totalFuel;
    }
};

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        n = len(roads) + 1
        graph = [[] for _ in range(n)]
        
        # 构建邻接表
        for a, b in roads:
            graph[a].append(b)
            graph[b].append(a)
        
        self.total_fuel = 0
        
        def dfs(node, parent):
            people = 1  # 当前节点的代表
            
            # 遍历所有子节点
            for child in graph[node]:
                if child != parent:
                    people += dfs(child, node)
            
            # 如果不是首都，计算到父节点的燃料成本
            if node != 0:
                self.total_fuel += (people + seats - 1) // seats
            
            return people
        
        dfs(0, -1)
        return self.total_fuel

public class Solution {
    private long totalFuel = 0;
    
    public long MinimumFuelCost(int[][] roads, int seats) {
        int n = roads.Length + 1;
        List<int>[] graph = new List<int>[n];
        
        // 初始化邻接表
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        // 构建邻接表
        foreach (int[] road in roads) {
            graph[road[0]].Add(road[1]);
            graph[road[1]].Add(road[0]);
        }
        
        DFS(0, -1, graph, seats);
        return totalFuel;
    }
    
    private int DFS(int node, int parent, List<int>[] graph, int seats) {
        int people = 1; // 当前节点的代表
        
        // 遍历所有子节点
        foreach (int child in graph[node]) {
            if (child != parent) {
                people += DFS(child, node, graph, seats);
            }
        }
        
        // 如果不是首都，计算到父节点的燃料成本
        if (node != 0) {
            totalFuel += (people + seats - 1) / seats;
        }
        
        return people;
    }
}

var minimumFuelCost = function(roads, seats) {
    const n = roads.length + 1;
    const graph = Array.from({length: n}, () => []);
    
    // 构建邻接表
    for (const [a, b] of roads) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    let totalFuel = 0;
    
    function dfs(node, parent) {
        let people = 1; // 当前节点的代表
        
        // 遍历所有子节点
        for (const child of graph[node]) {
            if (child !== parent) {
                people += dfs(child, node);
            }
        }
        
        // 如果不是首都，计算到父节点的燃料成本
        if (node !== 0) {
            totalFuel += Math.ceil(people / seats);
        }
        
        return people;
    }
    
    dfs(0, -1);
    return totalFuel;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)每个节点和边都只访问一次，n为节点数
空间复杂度O(n)邻接表存储图结构，递归栈深度最大为O(n)

相关题目