到达首都的最少油耗

难度: Medium

给你一棵 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⁵
roads.length == n - 1
roads[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
roads 表示一棵合法的树。
1 <= seats <= 10⁵

Submission

运行时间: 243 ms

内存: 70.4 MB

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        g = [[] for i in range(len(roads) + 1)]
        for e in roads:
            g[e[0]].append(e[1])
            g[e[1]].append(e[0])
        res = 0
        def dfs(cur, fa):
            nonlocal res
            peopleSum = 1 
            for ne in g[cur]:
                if ne != fa:
                    peopleCnt = dfs(ne, cur)
                    peopleSum += peopleCnt
                    res += (peopleCnt + seats - 1) // seats
            return peopleSum
        dfs(0, -1)
        return res

Explain

题解通过使用深度优先搜索（DFS）遍历树结构来计算从各个城市到首都的最少油耗。首先，构建邻接表表示城市之间的道路。在DFS中，每个节点（城市）计算它的子树中所有代表到达该节点所需的总人次。然后，根据每辆车的座位数，计算从该城市到其父节点（向首都方向）所需的最少油耗，即将子树的人次数除以座位数，向上取整。通过对所有子树的油耗求和，得到从所有城市到首都的总油耗。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        g = [[] for i in range(len(roads) + 1)]  # 创建邻接表
        for e in roads:  # 填充邻接表
            g[e[0]].append(e[1])
            g[e[1]].append(e[0])
        res = 0  # 初始化总油耗
        def dfs(cur, fa):  # 定义DFS函数
            nonlocal res  # 引用外部变量res
            peopleSum = 1  # 当前城市的代表
            for ne in g[cur]:  # 遍历当前城市的邻居
                if ne != fa:  # 避免向父节点回溯
                    peopleCnt = dfs(ne, cur)  # 递归计算子树中的代表数
                    peopleSum += peopleCnt  # 累加子树代表数
                    res += (peopleCnt + seats - 1) // seats  # 计算当前到父节点的油耗并累加到结果中
            return peopleSum  # 返回当前子树的总代表数
        dfs(0, -1)  # 从首都开始DFS
        return res  # 返回计算的结果

Explore

在题解中的实现里，邻接表是通过遍历所有道路信息来构建的。对于每一条道路，例如连接城市e[0]和e[1]，算法会在邻接表的e[0]索引下添加e[1]，同时在e[1]索引下添加e[0]。这样的处理确保了无向图的每条边在邻接表中被以双向连接的形式记录，从而使得从任一节点出发都能正确地访问到与之直接相连的其他节点。

在题解中使用`(peopleCnt + seats - 1) // seats`是为了实现向上取整的效果。由于每辆车的座位数是固定的，如果人数不能被座位数整除，就需要额外一辆车来运输剩下的人。通过添加`seats - 1`再整除`seats`，可以在不满足整除条件时自动增加一辆车，确保所有人都能被运输。直接使用`peopleCnt // seats`可能会导致在人数不完全被座位数整除时，计算得到的车辆数不足，无法运输所有的人。

在DFS函数的实现中，首都节点的父节点被初始化为-1，这是为了标记首都节点在递归遍历时的起始点。当遍历到首都节点时，由于其父节点值为-1，遍历函数会跳过向父节点的回溯，从而防止递归进入无限循环。这种设置简化了边界条件的处理，使得从首都开始的DFS可以自然而然地向外扩展到其他节点而不向不存在的父节点回溯。

在DFS的递归过程中，返回每个子树的代表数（`peopleSum`）是必要的，因为这允许每个节点能够知道其所有子节点累积的代表总数，从而计算从这些子节点到当前节点的油耗。如果使用全局变量来跟踪代表数，将难以区分来自各个子节点的代表数，进而无法准确计算每个子树对总油耗的贡献。通过返回每个子树的代表数，可以在每次递归调用后立即使用这个数值来更新总油耗，使得递归逻辑更加清晰和准确。