LeetCode 题解工作台
到达首都的最少油耗
给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。 0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [a i , b i ] ，表示城市 a i 和 b i 之间有一条 双向路 。 每个城市…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
根据题目描述，我们可以发现，所有车只会往首都（节点 ）开。 假设有一个节点 ，它的下一个节点为 ，节点 需要经过节点 才能到达首都。为了使得节点 的车辆（油耗）尽可能少，我们应该贪心地让节点 的子节点先汇聚到节点 ，然后按照座位数 分配车辆，那么到达节点 需要的最少车辆（油耗）就是 $\lceil \frac{sz}{seats} \rceil$。其中 表示以节点 为根的子树的节点…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 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 升汽油。
示例 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 <= 105roads.length == n - 1roads[i].length == 20 <= ai, bi < nai != biroads表示一棵合法的树。1 <= seats <= 105
解题思路
方法一：贪心 + DFS
根据题目描述，我们可以发现，所有车只会往首都（节点 ）开。
假设有一个节点 ，它的下一个节点为 ，节点 需要经过节点 才能到达首都。为了使得节点 的车辆（油耗）尽可能少，我们应该贪心地让节点 的子节点先汇聚到节点 ，然后按照座位数 分配车辆，那么到达节点 需要的最少车辆（油耗）就是 。其中 表示以节点 为根的子树的节点数。
我们从节点 开始进行深度优先搜索，用一个变量 统计以当前节点为根节点的子树的节点数。初始时 ，表示当前节点本身。然后我们遍历当前节点的所有子节点，对于每个子节点 ，我们递归地计算以 为根节点的子树的节点数 ，并将 累加到 上，然后我们将 累加到答案上。最后返回 。
时间复杂度 ，空间复杂度 。其中 为节点数。
class Solution:
def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
def dfs(a: int, fa: int) -> int:
nonlocal ans
sz = 1
for b in g[a]:
if b != fa:
t = dfs(b, a)
ans += ceil(t / seats)
sz += t
return sz
g = defaultdict(list)
for a, b in roads:
g[a].append(b)
g[b].append(a)
ans = 0
dfs(0, -1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each node and edge is visited once during DFS. Space complexity is O(n) for adjacency lists and recursive DFS stack. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks how to aggregate representatives efficiently in the tree.
- question_mark
Hints at considering car seat constraints and combining trips.
- question_mark
Probes for edge cases like single city or empty road list.
常见陷阱
外企场景- error
Forgetting to ceil the division when calculating trips, causing underestimation of fuel.
- error
Ignoring subtree aggregation, leading to redundant trips counted.
- error
Assuming bidirectional edges without properly marking visited nodes, causing infinite recursion.
进阶变体
外企场景- arrow_right_alt
Change seat capacity per car dynamically and recompute fuel.
- arrow_right_alt
Add weighted roads where fuel per road varies, requiring modified DFS.
- arrow_right_alt
Limit the number of trips per car per day, adding additional constraints on aggregation.