题目描述
思路解析动画文字版
记牢这一句:每条路的车数,等于这条路下面那棵子树的人数,除以座位数再向上取整。为什么可以一条边一条边地独立算,因为子树里的人不管怎么拼,最终都得挤过这唯一一条通向首都的路。下面把首都放在最上面,一层一层往下把人数数清。
全树总览 · 首都 0 在顶,座位 seats = 2：先把整棵树摆出来。城市 0 是首都,画在最上面,另外 7 座城顺着道路挂在它下面,一共 8 座城,每座城住着一位代表。每辆车坐 2 人,也就是 seats 等于 2。首都自己的代表已经在会场,不烧油;其余 7 位都要往上开。我们从最底下的城开始,一层层把子树里的人数数清,再折算每条路要几辆车。
从首都 0 出发 · 开始后序 DFS：从首都 0 出发做后序搜索。后序的意思是先把孩子那边全部数完,再回过头结算自己。首都下面挂着城市 1 和城市 2 两大分支,先钻进城市 1 那一支,一路往下探到最底端。
下行 · 进入城市 1：顺着道路往下走,来到城市 1。它底下还挂着更下级的城,别急着给它算账,先继续深入,把它子树里到底有多少位代表数清楚,再回来处理它头顶这条路。
末端城市 3 · 子树就 1 人：城市 3 是这条线的末端,底下没有别的城了。它这棵子树里就它自己一位代表,人数记 1。把它标成绿色,表示这一块已经数清,可以把这个 1 交还给它的父亲了。
结算路 · 城市 3 到城市 1：城市 3 这一支数好了,子树里一共 1 位代表。这些人都要挤过 城市 3 到城市 1 这一条路开向首都。每辆车坐 2 人:1 位代表还坐不满一车, 但也得开 1 辆车。这条路就耗 1 升油,累计油耗到 1 升。同时把这 1 位代表并进城市 1 的子树一起往上带。
下行 · 进入城市 4：顺着道路往下走,来到城市 4。它底下还挂着更下级的城,别急着给它算账,先继续深入,把它子树里到底有多少位代表数清楚,再回来处理它头顶这条路。
末端城市 6 · 子树就 1 人：城市 6 是这条线的末端,底下没有别的城了。它这棵子树里就它自己一位代表,人数记 1。把它标成绿色,表示这一块已经数清,可以把这个 1 交还给它的父亲了。
结算路 · 城市 6 到城市 4：城市 6 这一支数好了,子树里一共 1 位代表。这些人都要挤过 城市 6 到城市 4 这一条路开向首都。每辆车坐 2 人:1 位代表还坐不满一车, 但也得开 1 辆车。这条路就耗 1 升油,累计油耗到 2 升。同时把这 1 位代表并进城市 4 的子树一起往上带。
收拢 · 城市 4 子树共 2 人：城市 4 的下级都收拢完了,把它自己那位代表也算上,这棵子树一共 2 位代表。城市 4 标绿,表示它这一块彻底数清。接下来就轮到它头顶那条通往上级的路,用这 2 个人去折算要开几辆车。
结算路 · 城市 4 到城市 1：城市 4 这一支数好了,子树里一共 2 位代表。这些人都要挤过 城市 4 到城市 1 这一条路开向首都。每辆车坐 2 人:2 位代表正好坐满 1 辆车。这条路就耗 1 升油,累计油耗到 3 升。同时把这 2 位代表并进城市 1 的子树一起往上带。
收拢 · 城市 1 子树共 4 人：城市 1 的下级都收拢完了,把它自己那位代表也算上,这棵子树一共 4 位代表。城市 1 标绿,表示它这一块彻底数清。接下来就轮到它头顶那条通往上级的路,用这 4 个人去折算要开几辆车。
结算路 · 城市 1 到城市 0：城市 1 这一支数好了,子树里一共 4 位代表。这些人都要挤过 城市 1 到城市 0 这一条路开向首都。每辆车坐 2 人:4 位代表正好装满 2 辆车, 一个空座都不剩。这条路就耗 2 升油,累计油耗到 5 升。同时把这 4 位代表并进城市 0 的子树一起往上带。
下行 · 进入城市 2：顺着道路往下走,来到城市 2。它底下还挂着更下级的城,别急着给它算账,先继续深入,把它子树里到底有多少位代表数清楚,再回来处理它头顶这条路。
下行 · 进入城市 5：顺着道路往下走,来到城市 5。它底下还挂着更下级的城,别急着给它算账,先继续深入,把它子树里到底有多少位代表数清楚,再回来处理它头顶这条路。
末端城市 7 · 子树就 1 人：城市 7 是这条线的末端,底下没有别的城了。它这棵子树里就它自己一位代表,人数记 1。把它标成绿色,表示这一块已经数清,可以把这个 1 交还给它的父亲了。
结算路 · 城市 7 到城市 5：城市 7 这一支数好了,子树里一共 1 位代表。这些人都要挤过 城市 7 到城市 5 这一条路开向首都。每辆车坐 2 人:1 位代表还坐不满一车, 但也得开 1 辆车。这条路就耗 1 升油,累计油耗到 6 升。同时把这 1 位代表并进城市 5 的子树一起往上带。
收拢 · 城市 5 子树共 2 人：城市 5 的下级都收拢完了,把它自己那位代表也算上,这棵子树一共 2 位代表。城市 5 标绿,表示它这一块彻底数清。接下来就轮到它头顶那条通往上级的路,用这 2 个人去折算要开几辆车。
结算路 · 城市 5 到城市 2：城市 5 这一支数好了,子树里一共 2 位代表。这些人都要挤过 城市 5 到城市 2 这一条路开向首都。每辆车坐 2 人:2 位代表正好坐满 1 辆车。这条路就耗 1 升油,累计油耗到 7 升。同时把这 2 位代表并进城市 2 的子树一起往上带。
收拢 · 城市 2 子树共 3 人：城市 2 的下级都收拢完了,把它自己那位代表也算上,这棵子树一共 3 位代表。城市 2 标绿,表示它这一块彻底数清。接下来就轮到它头顶那条通往上级的路,用这 3 个人去折算要开几辆车。
结算路 · 城市 2 到城市 0：城市 2 这一支数好了,子树里一共 3 位代表。这些人都要挤过 城市 2 到城市 0 这一条路开向首都。每辆车坐 2 人:3 位代表, 先装满 1 辆车, 还剩 1 人得再开 1 辆, 一共 2 辆车。这条路就耗 2 升油,累计油耗到 9 升。同时把这 3 位代表并进城市 0 的子树一起往上带。
回到首都 · 全部到齐,总油耗 9 升：回到首都 0。它的两大分支都汇总完了:城市 1 那支的 4 人账已折成 2 升油,城市 2 那支的 3 人账折成 2 升油。连同下面各条小路,所有边的油耗加起来一共 9 升。首都自己的代表本就在会场,不用开车,不产生油耗。这 9 升就是最终答案。
回放 · 每条路的油耗相加 = 9：回头看一眼七条路各烧了多少油。靠近末端的五条路,人数都不超过 2,各开 1 辆车、各 1 升;剩下两条汇进首都的大路:城市 1 到首都 4 个人正好坐满 2 车,是 2 升;城市 2 到首都 3 个人得开 2 车,末车坐不满也算,还是 2 升。五个 1 加两个 2,正好 9 升。核心始终一句:每条路的车数,是它下面子树人数除以座位再向上取整。
边界想清:只有首都、没有外城则油耗 0;单条边 1 人就 1 车;链形结构越靠近首都汇的人越多,座位为 1 时车数按人数逐段累加。
面试重点:每条边唯一必经所以可独立取上整、ans 用 long 防溢出、时间空间都是 O(n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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复杂度
- 时间：O(n)，建无向邻接表遍历 roads 共 n 减 1 条边,是 O(n);后序 DFS 每座城恰好进出一次,每条边只被看常数次,合起来随城市数线性增长
- 空间：O(n)，按峰值算。邻接表存全部边是 O(n);递归栈深度等于树高,最坏是一条链时栈里排到接近 n 层。两者都是 O(n),不随规模平方增长
易错点
面试追问把动画讲成自己的话
追问这题为什么能一条边一条边地独立累加车数,而不用统筹全局调度?
追问子树人数 sz 用 int,累计答案 ans 却要用 long,这个取舍怎么想?
追问时间和空间复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树的堂兄弟节点 II
LeetCode 2641 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题