首都直达，如何省油？一日一练，跟着我走起！

方法一：贪心+深搜

思路

本题等价于给出了一棵根节点为 0 的树，树的每个节点上都有一个人，所有都需要通过汽车来到根节点 0。

为了消耗最少的汽油，一定要尽可能的 拼车。

于是可以从最外围的城市节点向 0 城市进发，每到达一个城市节点能拼车一定要拼车，于是需要统计每个城市节点 x 的子城市节点数，计算到达城市节点 x 的人数 peopleCnt。

到达城市节点 x 的最小油耗为

$$\lceil \frac{peopleCnt}{seats}\rceil$$

比如示例 2 的 2-3-1-0 段：

• 从城市 2 到城市 3 最少耗油 1 升，因为无人拼车；
• 从城市 3 到城市 1 最少耗油 1 升，因为目前到达城市 3 的有两人（到达一人+城市本身有一人），可以拼座位数为 2 的车，所以最小耗油 1 升；
• 从城市 1 到城市 0 最少耗油 2 升，因为目前到达城市 0 的有三人（到达两人+城市本身有一人），其中两人可以拼座位数为 2 的车，另外一个人需单独乘车，所以最小油耗为 2；
• 最后累加得到 2-3-1-0 段最小油耗为 4。

于是可以利用深度优先搜索的方法，从根节点即城市 0 深搜累加最小油耗得到最终答案。

算法

首先根据数组 roads 建立无向图 g，g[x] 表示的是与城市 x 相连的所有城市数组。

接着从根节点即城市 0 出发，进行深度优先搜索，在深搜的过程中更新答案 res，最后返回 res。

深搜的递归函数为 dfs，当前的城市为 x，其父节点城市为 fa：

• 递归出口为当前城市不再有任何子节点城市，直接返回 peopleSum = 1；
• 如果当前城市有子节点城市，遍历所有的子节点城市 y，得到从城市 y 到达当前城市的人数 peopleCnt，计算 (peopleCnt + seats - 1) / seats 得到从城市 y 到达当前城市的最小油耗，并到答案 res 中。并更新到达当前城市的人数 peopleSum += peopleCnt，最后返回 peopleSum。

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size();
        vector<vector<int>> g(n+1);

        for (auto road : roads) {
            int x = road[0], y = road[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }
        long long res = 0;
        function<int(int, int)> dfs = [&](int x, int fa) -> int {
            int peopleSum = 1;
            for (auto y : g[x]) {
                if (y != fa) {
                    int peopleCnt = dfs(y, x);
                    res += (peopleCnt + seats - 1) / seats;
                    peopleSum += peopleCnt;
                }
            }
            return peopleSum;
        };
        dfs(0, -1);
        return res;
    }
};

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组 roads 的长度。

空间复杂度：$O(n)$，主要为递归（深度优先搜索）所需要的空间开销。

---