题目描述
思路解析动画文字版
记牢这套:一遍标 Bob 的时间戳,一遍让 Alice 按时间比门。先小于就抢先、相等就平分、大于就落空。下面先把 Bob 的时间戳标出来。
开局 · Alice 在根 0,Bob 在叶子 6：先看清这棵树。根 0 在最上面,它有两个孩子 1 和 2,1 又带着叶子 3、4,2 又带着叶子 5、6。Alice 站在根 0,标成紫色;Bob 站在叶子 6,标成红色。接下来他俩各自出发,Alice 往下钻找叶子,Bob 往上爬奔根 0。
看清 · Alice 的四个可能终点是叶子 3,4,5,6：Alice 最终一定停在某片叶子上,这棵树的叶子是 3、4、5、6,对应四条从根出发的路。她要在这四条里挑净得分最高的一条。分值受一件事影响:每扇门是不是被 Bob 抢先开了。所以我们得先知道 Bob 什么时候到哪儿。
两步走 · 先标 Bob 时间戳,再让 Alice 比门：整道题拆成两步。第一步让 Bob 先动:从他所在的 6 号点出发,找到通往根 0 的唯一一条路,把这条路上每个点标上时间戳。第二步再让 Alice 从根往下走,拿她的到达时间和这些时间戳比。我们先把所有点的时间戳都当成无穷大,再往 Bob 走过的点上填真实值。
dfs1 · Bob 起点 6,时间戳 ts[6] = 0：Bob 从 6 号点出发,第 0 秒他就站在这里,所以 6 号点的时间戳记成 0。时间戳的含义就是:Bob 最早在第几秒踏上这个点。他要奔根 0,6 只跟 2 相连,于是下一步只能走到 2。
dfs1 · Bob 走到 2,时间戳 ts[2] = 1：Bob 从 6 迈一步到 2,这是第 1 秒,所以 2 号点的时间戳记成 1。走过的 6 号点标成蓝色,表示时间戳已经盖好。2 号点上面连着根 0,Bob 继续往上爬。
dfs1 · Bob 到达根 0,时间戳 ts[0] = 2,停：Bob 从 2 再迈一步到根 0,这是第 2 秒,时间戳记成 2。规则说 Bob 一到根 0 就停下不再动。到这里 Bob 的整条路线 6、2、0 三个点的时间戳全部盖好了,分别是 0、1、2。
dfs1 · 路线外的 1,3,4,5 时间戳保持无穷大：Bob 的路只碰到 6、2、0 这三个点。1、3、4、5 这几个点 Bob 根本不会经过,它们的时间戳一直是当初设的无穷大。无穷大是个很关键的信号:它表示 Bob 永远走不到这里,所以 Alice 到了一定是先开门,能独享整份分。
dfs1 完成 · 全部时间戳一览：把七个点的时间戳汇总:ts[0] 是 2、ts[2] 是 1、ts[6] 是 0,这三点在 Bob 路上;ts[1]、ts[3]、ts[4]、ts[5] 都是无穷大。第一步到此结束。接下来第二步,Alice 从根 0 往下走,每到一个点就拿她的到达秒数去和这张表比。
dfs2 · Alice 到根 0,秒数 t = 0,比 ts = 2：Alice 出发,第 0 秒她就在根 0。根 0 的时间戳是 2,也就是 Bob 要第 2 秒才到。Alice 的 0 比 2 小,她抢先开了这扇门,整份分归她。0 号门的分值是 -4。
dfs2 · 0 号门归 Alice,v 加 -4 = -4：把 0 号门的 -4 加进这条路的得分,v 从 0 变成 -4。根 0 标成绿色表示 Alice 已经拿过它的分。根有两个孩子 1 和 2,按顺序先走 1 这一支。
dfs2 · Alice 到 1,秒数 t = 1,比 ts = ∞：Alice 走到 1,这是第 1 秒。1 号点不在 Bob 的路上,时间戳是无穷大,Alice 的 1 当然更小,她抢先开门。1 号门分值是 2。
dfs2 · 1 号门归 Alice,v 加 2 = -2：1 号门的 2 加进来,v 从 -4 变成 -2。1 号点变绿。它带着两片叶子 3 和 4,先钻左边的 3。
dfs2 · 叶子 3,秒数 t = 2,独享 6,路径得分 4：到叶子 3,第 2 秒。它 ts 是无穷大,Alice 抢先,独享 6,v 从 -2 变成 4。3 是叶子,Alice 到这就停了。这条 0 到 1 到 3 的路走完,得分 4,记成第一个候选。
dfs2 · 回到 1 走叶子 4,独享 -10,路径得分 -12：回到 1,换走另一片叶子 4,还是第 2 秒。4 也不在 Bob 路上,Alice 独享它的门,可这门分值是 -10,是扣分。v 从 1 号点走下来的 -2 变成 -12。这条 0 到 1 到 4 的路得分只有 -12,远不如走 3。
dfs2 · 1 这一支走完,回到根 0 换走孩子 2：1 这一支两片叶子都试过了,得分是 4 和 -12。DFS 回到根 0,注意得分 v 会退回根这里的 -4,因为换路要从根重新往下累加。现在走根的另一个孩子 2。前面 2 号点的时间戳是 1,好戏来了。
dfs2 · Alice 到 2,秒数 t = 1,ts 也是 1,同时到：Alice 第 1 秒走到 2,而 Bob 的时间戳也正好是 1。两人同一秒撞到同一扇门,规则说这时平分。2 号门分值是 8,平分就是各拿一半,Alice 只加 8 的一半。
dfs2 · 2 号门平分,v 加 8 的一半 4 = 0：8 的一半是 4,加进来 v 从 -4 变成 0。这就是平分:同一秒到,分值对半分。2 号点变绿。它带着叶子 5 和 6,先走 5。
dfs2 · 叶子 5,独享 10,路径得分 10(目前最好)：走到叶子 5,第 2 秒。5 不在 Bob 路上,Alice 独享 10,v 从 0 变成 10。这条 0 到 2 到 5 的路得分 10,比前面所有候选都高,当前最好成绩刷新成 10。
dfs2 · Alice 到 6,秒数 t = 2,ts = 0,门早被 Bob 开：回到 2 换走叶子 6。Alice 第 2 秒才到 6,可 Bob 的时间戳是 0,他一开始就在这里、早把门开了。门开过就不再计分,Alice 到 6 这一格一分都拿不到。哪怕 6 号门写着 12 的加分,也和她无关。
dfs2 · 叶子 6 落空,加 0,路径得分 0：6 号门落空,加 0,这条 0 到 2 到 6 的路得分停在 0。它是个候选 0,但比不过走 5 的 10。最好成绩仍然是 10。四片叶子全试完了。
结算 · 四个叶子候选比大小：把四片叶子的成绩摆一起:走 3 得 4,走 4 得 -12,走 5 得 10,走 6 得 0。取最大的,答案就是 10,对应 Alice 走 0 到 2 再到 5 这一条。
完成 · 最优路径 0 → 2 → 5,答案 = 10：高亮这条最优路 0 到 2 到 5:根 0 抢先拿 -4,到 2 和 Bob 平分拿 4,到叶子 5 抢先拿 10,合起来 -4 加 4 加 10 正好是 10。整道题就是一遍标 Bob 时间戳,一遍让 Alice 按时间比门取最大。
边界想清:只有一条路时直接顺着算;Bob 起点那扇门 Alice 永远落空;链上正中间那点常常是两人同时到、要平分。
面试重点:两遍 DFS 标时间戳再比时间、Bob 路径也可用父指针回溯求、偶数保证平分不出小数。
参考代码
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 mostProfitablePath( self, edges: List[List[int]], bob: int, amount: List[int] ) -> int: def dfs1(i, fa, t): if i == 0: ts[i] = min(ts[i], t) return True for j in g[i]: if j != fa and dfs1(j, i, t + 1): ts[j] = min(ts[j], t + 1) return True return False def dfs2(i, fa, t, v): if t == ts[i]: v += amount[i] // 2 elif t < ts[i]: v += amount[i] nonlocal ans if len(g[i]) == 1 and g[i][0] == fa: ans = max(ans, v) return for j in g[i]: if j != fa: dfs2(j, i, t + 1, v) n = len(edges) + 1 g = defaultdict(list) ts = [n] * n for a, b in edges: g[a].append(b) g[b].append(a) dfs1(bob, -1, 0) ts[bob] = 0 ans = -inf dfs2(0, -1, 0, 0) return ans复杂度
- 时间：O(n)，n 个点、n 减 1 条边。建邻接表 O(n);dfs1 找 Bob 的路,每条边最多走一次;dfs2 遍历整棵树每个点一次,每步都是常数比较。两遍都随节点数线性,合起来 O(n)
- 空间：O(n)，按峰值算。邻接表 O(n)、时间戳数组 ts O(n);递归栈深度是树高 h,最坏树退化成一条链时 h 达到 O(n)。三项都在 O(n) 量级
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问Bob 的时间戳除了 DFS 还能怎么求?
追问为什么两人同时到能保证平分不出小数?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
逐层排序二叉树所需的最少操作数目
LeetCode 2471 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题