How does depth-first search apply to 'Most Profitable Path in a Tree'?

DFS is used to traverse the tree, calculating Alice's net profit at each node while considering Bob's fixed path towards node 0.

What happens if Alice and Bob meet at the same node?

If Alice and Bob meet at the same node, they share the reward, which impacts Alice's net income based on the game's rules.

What is the most important factor in maximizing Alice's profit?

The most important factor is predicting Alice's path while considering Bob’s fixed path and ensuring Alice reaches profitable nodes first.

Are there any edge cases to consider in this problem?

Yes, consider scenarios where Bob reaches a node before Alice, and Alice cannot maximize the reward from that node.

How does Bob's fixed path influence the solution?

Bob's fixed path dictates when Alice can move to a node and open its gate, which directly influences her ability to maximize profit.

#2467

Medium

auto_awesome图·DFS·traversal

LeetCode 题解工作台

树上最大得分和路径

一个 n 个节点的无向树，节点编号为 0 到 n - 1 ，树的根结点是 0 号节点。给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a i , b i ] ，表示节点 a i 和 b i 在树中有一条边。在每一个节点 i 处有一扇门。同时给你一个都是偶数的…

数组树深度优先搜索广度优先搜索图

题目描述

一个 n 个节点的无向树，节点编号为 0 到 n - 1 ，树的根结点是 0 号节点。给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a_i, b_i] ，表示节点 a_i 和 b_i 在树中有一条边。

在每一个节点 i 处有一扇门。同时给你一个都是偶数的数组 amount ，其中 amount[i] 表示：

如果 amount[i] 的值是负数，那么它表示打开节点 i 处门扣除的分数。
如果 amount[i] 的值是正数，那么它表示打开节点 i 处门加上的分数。

游戏按照如下规则进行：

一开始，Alice 在节点 0 处，Bob 在节点 bob 处。
每一秒钟，Alice 和 Bob 分别移动到相邻的节点。Alice 朝着某个 叶子结点 移动，Bob 朝着节点 0 移动。
对于他们之间路径上的 每一个 节点，Alice 和 Bob 要么打开门并扣分，要么打开门并加分。注意：
- 如果门 已经打开 （被另一个人打开），不会有额外加分也不会扣分。
- 如果 Alice 和 Bob 同时到达一个节点，他们会共享这个节点的加分或者扣分。换言之，如果打开这扇门扣 c 分，那么 Alice 和 Bob 分别扣 c / 2 分。如果这扇门的加分为 c ，那么他们分别加 c / 2 分。
如果 Alice 到达了一个叶子结点，她会停止移动。类似的，如果 Bob 到达了节点 0 ，他也会停止移动。注意这些事件互相独立，不会影响另一方移动。

请你返回 Alice 朝最优叶子结点移动的最大净得分。

示例 1：

输入：edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
输出：6
解释：
上图展示了输入给出的一棵树。游戏进行如下：
- Alice 一开始在节点 0 处，Bob 在节点 3 处。他们分别打开所在节点的门。
  Alice 得分为 -2 。
- Alice 和 Bob 都移动到节点 1 。
  因为他们同时到达这个节点，他们一起打开门并平分得分。
  Alice 的得分变为 -2 + (4 / 2) = 0 。
- Alice 移动到节点 3 。因为 Bob 已经打开了这扇门，Alice 得分不变。
  Bob 移动到节点 0 ，并停止移动。
- Alice 移动到节点 4 并打开这个节点的门，她得分变为 0 + 6 = 6 。
现在，Alice 和 Bob 都不能进行任何移动了，所以游戏结束。
Alice 无法得到更高分数。

示例 2：

输入：edges = [[0,1]], bob = 1, amount = [-7280,2350]
输出：-7280
解释：
Alice 按照路径 0->1 移动，同时 Bob 按照路径 1->0 移动。
所以 Alice 只打开节点 0 处的门，她的得分为 -7280 。

提示：

2 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
edges 表示一棵有效的树。
1 <= bob < n
amount.length == n
amount[i] 是范围 [-10⁴, 10⁴] 之间的一个偶数。

lightbulb

解题思路

方法一：两次 DFS

根据题意，我们可以知道，Bob 的移动路径是固定的，即从节点 $bob$ 出发，最终到达节点 $0$ 。因此，我们可以先跑一遍 DFS，求出 Bob 到达每个节点的时间，记在数组 $ts$ 中。

然后我们再跑一遍 DFS，求出 Alice 每条移动路径的最大得分，我们记 Alice 到达节点 $i$ 的时间为 $t$ ，当前累计得分为 $v$ ，那么 Alice 在经过节点 $i$ 处后，累计的分数有三种情况：

Alice 到达节点 $i$ 的时间 $t$ 与 Bob 到达节点 $i$ 的时间 $ts[i]$ 相同，那么 Alice 和 Bob 同时打开节点 $i$ 处的门，Alice 获得的分数为 $v + \frac{amount[i]}{2}$ ；
Alice 到达节点 $i$ 的时间 $t$ 小于 Bob 到达节点 $i$ 的时间 $ts[i]$ ，那么 Alice 打开节点 $i$ 处的门，Alice 获得的分数为 $v + amount[i]$ 。
Alice 到达节点 $i$ 的时间 $t$ 大于 Bob 到达节点 $i$ 的时间 $ts[i]$ ，那么 Alice 不打开节点 $i$ 处的门，Alice 获得的分数为 $v$ ，即不变。

当 Alice 到达叶子节点时，更新最大得分。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

class 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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidates should demonstrate familiarity with tree traversal techniques, particularly depth-first search.
question_mark
Ensure candidates account for the fixed nature of Bob's path and how it impacts Alice's net income.
question_mark
Watch for correct handling of edge cases where Alice and Bob may meet at nodes or where Alice has no opportunity to maximize profit.

warning

常见陷阱

外企场景

error
Ignoring the fixed path of Bob and treating it as a dynamic variable.
error
Failing to account for the case when Alice and Bob meet at a node, splitting the reward.
error
Overcomplicating the solution, such as using unnecessary data structures or algorithms that increase time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the problem to consider multiple starting positions for Bob, testing the algorithm's flexibility.
arrow_right_alt
Add constraints where certain nodes provide negative rewards, forcing more strategic decisions about paths.
arrow_right_alt
Incorporate a time limit for how long Alice can travel, testing the solution’s efficiency under time pressure.

help

常见问题

外企场景

继续练习

#2368 受限条件下可到达节点的数目 #2458 移除子树后的二叉树高度 #2328 网格图中递增路径的数目