『LeetCode』2477 到达首都的最少油耗

题目

给你一棵 \(n\) 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 \(0\) 到 \(n - 1\) ，且恰好有 \(n - 1\) 条路。\(0\) 是首都。给你一个二维整数数组 \(roads\) ，其中 \(roads[i] = [a^{i}, b^{i}]\) ，表示城市 \(a^{i}\) 和 \(b^{i}\) 之间有一条 双向路 。

每个城市里有一个代表，他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

示例 1：

输入：roads = [[0,1],[0,2],[0,3]], seats = 5
输出：3
解释：
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 2 直接到达首都，消耗 1 升汽油。
- 代表 3 直接到达首都，消耗 1 升汽油。
最少消耗 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 升汽油。

示例 3：

输入：roads = [], seats = 1
输出：0
解释：没有代表需要从别的城市到达首都。

提示：

\(1 <= n <= 10^{5}\)
\(roads.length == n - 1\)
\(roads[i].length == 2\)
\(0 <= a^{i}, b^{i} < n\)
\(a^{i} != b^{i}\)
\(roads\) 表示一棵合法的树。
\(1 <= seats <= 10^{5}\)

题解

【到达首都的最少油耗】简单递归

DFS

由于路径是树，倒也不是很复杂，这说明任意一个点到根节点的路径有且只有一条，也就不存在路径选择的问题。我们从叶子节点出发，逐级向上归并并计算乘车数量即可。具体来说，将结点 0 视为根节点，从叶子节点出发，向父节点前进，到达父节点后，统计其子树所有结点的人数和，再继续想父节点前进，这是个递归的过程。用程序化一点的语义表述为：

输入：当前结点；输出：该结点及其子树的人数，以及其子树中结点汇聚到该结点需要的乘车数
对于给定结点，先统计其子树的人数和从其子树到该结点的乘车数量
将乘车数量累加到结果并向上层结点返回人数

其实就是一个统计树中结点数量的简单递归，递归过程插入计算乘车数量即可

# Code language: Python
class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        n = len(roads) + 1
        tree = [[] for _ in range(n)]
        for u, v in roads:
            tree[u].append(v)
            tree[v].append(u)
        vis = [False] * n
        def dfs(cur) -> int:
            vis[cur] = True
            cnt, ans = 1, 0
            for nxt in tree[cur]:
                if vis[nxt]:
                    continue
                v, s = dfs(nxt)
                ans += (v + seats - 1) // seats + s
                cnt += v
            return cnt, ans # 返回 人数，累计乘车数量
        
        return dfs(0)[1]

// Code language: Java
class Solution {
    long ans = 0;
    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        ans = 0;
        List<Integer>[] tree = new List[n];
        for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
        for (var r: roads) {
            int u = r[0], v = r[1];
            tree[u].add(v);
            tree[v].add(u);
        }
        boolean[] vis = new boolean[n];
        dfs(0, tree, vis, seats);
        return ans;
    }

    int dfs(int cur, List<Integer>[] tree, boolean[] vis, int seats) {
        vis[cur] = true;
        int cnt = 1;
        for (int nxt: tree[cur]) {
            if (vis[nxt]) continue;
            int v = dfs(nxt, tree, vis, seats);
            ans += (v + seats - 1) / seats;
            cnt += v;
        }
        return cnt;
    }
}

// Code language: C++
class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        vector<vector<int>> tree(n, vector<int>(0));
        for (auto& r: roads) {
            int u = r[0], v = r[1];
            tree[u].emplace_back(v);
            tree[v].emplace_back(u);
        }
        long long ans = 0;
        vector<int> vis(n, 0);
        function<int(int)> dfs = [&](int cur) {
            int cnt = 1;
            vis[cur] = 1;
            for (int nxt: tree[cur]) {
                if (vis[nxt] == 1) continue;
                int v = dfs(nxt);
                ans += (v + seats - 1) / seats;
                cnt += v;
            }
            return cnt;
        };
        dfs(0);
        return ans;
    }
};

// Code language: Go
func minimumFuelCost(roads [][]int, seats int) (ans int64) {
    n := len(roads) + 1
    tree := make([][]int, n)
    for _, r := range roads {
        u, v := r[0], r[1]
        tree[u] = append(tree[u], v)
        tree[v] = append(tree[v], u)
    }
    vis := make([]int, n)
    var dfs func(int) int
    dfs = func(cur int) int {
        cnt := 1
        vis[cur] = 1
        for _, nxt := range tree[cur] {
            if vis[nxt] == 1 {
                continue
            }
            v := dfs(nxt)
            ans += int64((v + seats - 1) / seats)
            cnt += v
        }
        return cnt
    }
    dfs(0)
    return
}

时间复杂度: \(O(n)\), 其中 \(n\) 是城市数量，即 \(roads\) 的长度 + 1
空间复杂度: \(O(n)\), 建图及 vis 数组

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』2477 到达首都的最少油耗

题目

标签

题解

DFS