#2467

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Most Profitable Path in a Tree

Solve the 'Most Profitable Path in a Tree' problem using graph traversal and depth-first search techniques to maximize Alice's net income.

array tree depth first search breadth first search graph

Problem Statement

You are given an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0. The tree's edges are represented as a 2D array where each edge is a connection between two nodes. Additionally, each node has a gate, and you are provided an array of even integers representing the profit at each node. Alice starts at node 0, while Bob starts at a given node.

The game proceeds with Alice and Bob simultaneously opening gates at nodes they reach, but Bob always moves toward node 0. The goal is to determine Alice's maximum net profit after both have moved through the tree. Alice's profit is adjusted based on the amount at the nodes, and if both Alice and Bob reach a node together, they split the reward.

Examples

Example 1

Input: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]

Output: 6

The above diagram represents the given tree. The game goes as follows:

Alice is initially on node 0, Bob on node 3. They open the gates of their respective nodes. Alice's net income is now -2.
Both Alice and Bob move to node 1. Since they reach here simultaneously, they open the gate together and share the reward. Alice's net income becomes -2 + (4 / 2) = 0.
Alice moves on to node 3. Since Bob already opened its gate, Alice's income remains unchanged. Bob moves on to node 0, and stops moving.
Alice moves on to node 4 and opens the gate there. Her net income becomes 0 + 6 = 6. Now, neither Alice nor Bob can make any further moves, and the game ends. It is not possible for Alice to get a higher net income.

Example 2

Input: edges = [[0,1]], bob = 1, amount = [-7280,2350]

Output: -7280

Alice follows the path 0->1 whereas Bob follows the path 1->0. Thus, Alice opens the gate at node 0 only. Hence, her net income is -7280.

Constraints

2 <= n <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges represents a valid tree.
1 <= bob < n
amount.length == n
amount[i] is an even integer in the range [-104, 104].

Solution Approach

DFS Traversal

To solve this problem efficiently, use depth-first search (DFS) to explore the tree. Starting from Alice's node, you will traverse the tree recursively, calculating the net income at each node. Track the paths Alice and Bob would take, accounting for simultaneous gate openings and their respective rewards.

Bob's Path Consideration

Since Bob always moves toward node 0, his movements are fixed. This allows you to predict when Alice and Bob will meet at nodes. Adjust Alice's income based on the rules when both arrive at the same node at the same time.

Maximizing Profit

While traversing the tree, track Alice's net income and make decisions that maximize her profit. When Alice moves to a node, check if her income can increase by opening the gate there. If Bob arrives at the node before her, Alice won't receive the full reward, and her income won't change.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n), where n is the number of nodes in the tree, due to the DFS traversal. Space complexity is also O(n) because of the recursive call stack and the storage needed for the tree structure.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Two DFS Traversals

According to the problem, we know that Bob's moving path is fixed, that is, starting from node $bob$ and finally reaching node $0$. Therefore, we can first run a DFS to find out the time it takes for Bob to reach each node, which we record in the array $ts$.

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

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

Continue Practicing

#2368 reachable nodes with restrictions #2458 height of binary tree after subtree removal queries #2328 number of increasing paths in a grid