2467. Most Profitable Path in a Tree


Problem Description

In this problem, there is an undirected tree with n nodes, each labeled from 0 to n - 1. The tree is rooted at node 0. The input includes a 2D integer array edges where each entry edges[i] represents an edge between two nodes a_i and b_i, forming the tree's structure.

Each node i in the tree has a gate with an associated cost or a reward. The cost or reward for each node is given by the array of even integers amount. If amount[i] is negative, it represents the cost to open the gate, and if it's positive, it represents the reward one receives when the gate is opened.

Alice starts at the root node (node 0), and Bob begins at node bob. The game progresses with both Alice and Bob moving to an adjacent node every second: Alice heads towards a leaf node, while Bob moves toward the root node 0. When passing through a node, they have to either pay the cost or receive a reward for opening the gate. If Alice and Bob arrive at a node at the same time, they split the cost or reward. Once Alice reaches a leaf node, she stops moving, and similarly for Bob, when he arrives at node 0.

The objective is to determine the maximum net income that Alice can achieve by selecting the optimal path to a leaf node.

Intuition

To arrive at the solution, consider the following steps:

  1. First, we need to track the time it takes for Bob to reach each node from his starting position. This is crucial because it determines when Alice and Bob will share the cost or reward at a gate.

  2. Once we have Bob's times to reach each node recorded, Alice can start her journey from the root node. As she progresses, at each node, she needs to decide if she has to pay the full cost, receive the full reward, or share it with Bob, depending on whether Bob has already passed that node.

  3. We use Depth-First Search (DFS) to explore the tree. Start by performing DFS from Bob's starting node to calculate and store the time steps required for Bob to reach each node (ts array). During this search, we mark the shortest path from Bob's node to the root node.

  4. The next step is to conduct another DFS starting from Alice's node (node 0). Here we accumulate the total value that Alice can collect or pay, taking into consideration her sharing costs or rewards with Bob. In each step, compare the steps taken with Bob's time to reach the same node, and adjust the net income accordingly.

  5. While performing DFS for Alice, if a leaf node is reached, record the net income. We're interested in maximizing Alice's net income, so we keep track of the maximum value found along the way.

  6. Once all paths to leaf nodes have been assessed, return the maximum net income Alice can achieve, which represents the optimal path she should take to maximize her earnings.

In summary, the solution involves understanding the traversal times of both Alice and Bob through the tree while determining the shared or individual financial interactions at each gate, ultimately yielding the path that maximizes Alice's net income.

Solution Approach

The implementation of the solution makes use of two Depth-First Search (DFS) traversals on the tree to maximize Alice's net income. Here's how it is done step-by-step:

  1. A dictionary g is created using defaultdict(list), which serves as an adjacency list to represent the tree, where each key corresponds to a node, and the value is a list of adjacent nodes.

  2. An array ts is initialized with n elements, each set to n (a value higher than any possible travel time), which will be used to store the minimum time steps for Bob to reach every node from his starting position.

  3. The dfs1 function is defined to perform the initial DFS starting from Bob's node. This function recursively explores the tree, tracking the time steps t taken to reach each node. If the current node is 0 (the root), it updates the corresponding ts value with the minimum time steps taken. This function also marks the shortest path from Bob's starting position to the root by updating the ts values along the way.

  4. The dfs2 function is defined for Alice's DFS traversal. This function takes the current node i, its parent fa, the current time steps t, and the current net value v collected by Alice as arguments. It compares Alice's time steps with Bob's time from the ts array. If Alice and Bob reach the node at the same time, the amount is equally shared; if Alice arrives before Bob, she gets the entire amount. It's important to account for this sharing policy in the net value calculation.

  5. The code begins Alice's traversal by initializing ans with -inf, marking no income initially. It calls dfs2 starting from node 0.

  6. During Alice's DFS, when a leaf node is reached (a node with only one adjacent node that is its parent), we check if the net value v is greater than ans. If it is, we update ans with the new maximum net income Alice can achieve.

  7. After exploring all possible paths to leaf nodes, the value of ans will hold the maximum net income Alice can obtain. This value is returned as the solution.

The core algorithm relies on the efficient traversal of trees using DFS and leveraging the decision process at each gate to maximize the net income for Alice. The use of recursion in DFS is crucial to explore all paths easily, and the use of a simple array to keep track of Bob's travel times allows for constant-time lookups when determining who pays or receives rewards at each gate.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's take a small example to illustrate the solution approach. Assume we have a tree with n = 5 nodes, and Bob starts at node b = 4. The array edges representing the edges of this tree is [[0,1], [0,2], [1,3], [1,4]]. The amount array with the cost or reward for opening each gate at the nodes is [-3, -2, 4, 1, 5].

Here's how we can visualize our tree and the rewards/costs:

1   0(-3)
2  / \
3 1   2(4)
4/-\
53(1)4(5)

Now, let's walk through the solution steps:

  1. We create an adjacency list from the edges array.

    1g = {0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1], 4: [1]}
  2. We initialize the time steps ts array, which will store how long it takes for Bob to reach each node starting from node 4.

    1ts = [5, 5, 5, 5, 5]  // since n = 5
  3. Perform DFS from Bob's starting node 4 to populate ts with the correct time steps, marking the shortest path from node 4 to the root node 0:

    1After dfs1, ts = [2, 1, 5, 5, 0]

    This reflects that Bob starts at node 4, takes 1 second to get to node 1, and another second to get to the root node 0. He hasn't visited nodes 2 and 3, so they remain at the initialized, non-reachable value of 5.

  4. Perform DFS from the root node 0 for Alice's traversal:

    • Start at node 0 which has a cost of -3. Since Bob will be at the root after 2 seconds and Alice is already there, the cost is only on Alice, so her net value starts at -3.
    • Moving to node 1, the cost is -2. Since it takes 1 second for Alice to move and Bob takes 1 second to get there from his starting node, they both share the movement. The cost to Alice is now -3 - (-1) = -2.
    • From node 1, Alice has two possible moves to node 3 or node 4.
    • If she moves towards node 3 (reward of 1) and collects the full reward because Bob doesn't reach here. This option gives Alice -2 + 1 = -1 net value.
    • If she moves toward node 4 (reward of 5) and shares this reward with Bob, because he starts from there, both receive 2.5. Alice's net value would be -2 + 2.5 = 0.5.
  5. As Alice's traversal continues, she only needs to decide once to go to either node 3 or node 4, as those are leaf nodes. She picks the path which gives her the maximum net income.

  6. After exploring both options, the maximum net income Alice can achieve is 0.5, which comes from sharing the gate reward at node 4 with Bob. Thus, the optimal path for her would be 0 -> 1 -> 4.

The returned value is 0.5, indicating the maximum net income Alice can obtain. This walkthrough demonstrates how two separate DFS traversals are used to compute Bob’s travel times and maximize Alice’s net income by making the right choices at each node.

Python Solution

1from typing import List
2from collections import defaultdict
3
4class Solution:
5    def mostProfitablePath(self, edges: List[List[int]], start: int, amount: List[int]) -> int:
6        # Initialize Depth-First Search to determine the number of steps to reach Node 0 from start
7        def dfs_time_to_reach(i, prev, t):
8            # If we've reached Node 0, update the time and return True
9            if i == 0:
10                time_to_reach[i] = min(time_to_reach[i], t)
11                return True
12            # Traverse the graph
13            for neighbor in graph[i]:
14                if neighbor != prev and dfs_time_to_reach(neighbor, i, t + 1):
15                    # Update the time for each node as we find a shorter path
16                    time_to_reach[neighbor] = min(time_to_reach[neighbor], t + 1)
17                    return True
18            return False
19
20        # Perform DFS to calculate the most profitable value while traveling towards Node 0
21        def dfs_max_profit(i, prev, t, current_profit):
22            # Collect the profit according to the rules described
23            if t == time_to_reach[i]:
24                current_profit += amount[i] // 2
25            elif t < time_to_reach[i]:
26                current_profit += amount[i]
27            nonlocal max_profit
28            # If it's a leaf node, update the max_profit if the current_profit is higher
29            if len(graph[i]) == 1 and graph[i][0] == prev:
30                max_profit = max(max_profit, current_profit)
31                return
32            # Continue DFS on the graph
33            for neighbor in graph[i]:
34                if neighbor != prev:
35                    dfs_max_profit(neighbor, i, t + 1, current_profit)
36
37        num_nodes = len(edges) + 1
38        graph = defaultdict(list)
39        time_to_reach = [num_nodes] * num_nodes  # Initialize with a large number
40        # Convert edge list to a graph
41        for a, b in edges:
42            graph[a].append(b)
43            graph[b].append(a)
44        # Start DFS to determine time to reach Node 0
45        dfs_time_to_reach(start, -1, 0)
46        time_to_reach[start] = 0  # Set the start node time to 0
47        max_profit = float('-inf')  # Initialize maximum profit as negative infinity
48        # Start DFS to determine max profit
49        dfs_max_profit(0, -1, 0, 0)
50        return max_profit
51

Java Solution

1class Solution {
2    private List<Integer>[] graph;
3    private int[] profitAtNode;
4    private int[] timeStamps;
5    private int maximumProfit = Integer.MIN_VALUE;
6
7    // Main method to find the most profitable path for Bob from a given start node
8    public int mostProfitablePath(int[][] edges, int bobStartNode, int[] profit) {
9        int n = edges.length + 1;
10        graph = new List[n];
11        timeStamps = new int[n];
12        profitAtNode = profit;
13        // Initialize lists for the adjacency representation of the graph and fill timestamps with an upper bound.
14        Arrays.setAll(graph, k -> new ArrayList<>());
15        Arrays.fill(timeStamps, n);
16        for (var edge : edges) {
17            int nodeA = edge[0], nodeB = edge[1];
18            graph[nodeA].add(nodeB);
19            graph[nodeB].add(nodeA);
20        }
21        // Run the first DFS for timestamp assignment
22        dfsAssignTimestamps(bobStartNode, -1, 0);
23        timeStamps[bobStartNode] = 0;  // Set the start node's timestamp to 0
24        // Run the second DFS to calculate the maximum profit
25        dfsCalculateProfit(0, -1, 0, 0);
26        return maximumProfit;
27    }
28
29    // Helper method for the first DFS to assign timestamps
30    private boolean dfsAssignTimestamps(int currentNode, int parent, int timestamp) {
31        if (currentNode == 0) {
32            timeStamps[currentNode] = Math.min(timeStamps[currentNode], timestamp);
33            return true;
34        }
35        for (int nextNode : graph[currentNode]) {
36            if (nextNode != parent && dfsAssignTimestamps(nextNode, currentNode, timestamp + 1)) {
37                timeStamps[nextNode] = Math.min(timeStamps[nextNode], timestamp + 1);
38                return true;
39            }
40        }
41        return false;
42    }
43
44    // Helper method for the second DFS to calculate the maximum profit
45    private void dfsCalculateProfit(int currentNode, int parent, int timestamp, int currentProfit) {
46        // Partial profit is halved when on the most profitable path (determined by timestamp)
47        if (timestamp == timeStamps[currentNode]) {
48            currentProfit += profitAtNode[currentNode] >> 1;
49        } else if (timestamp < timeStamps[currentNode]) {
50            // If this node is reached earlier, add full profit
51            currentProfit += profitAtNode[currentNode];
52        }
53        // If this node is a leaf node, update the maximum profit and return
54        if (graph[currentNode].size() == 1 && graph[currentNode].get(0) == parent) {
55            maximumProfit = Math.max(maximumProfit, currentProfit);
56            return;
57        }
58        // Continue DFS for subsequent nodes
59        for (int nextNode : graph[currentNode]) {
60            if (nextNode != parent) {
61                dfsCalculateProfit(nextNode, currentNode, timestamp + 1, currentProfit);
62            }
63        }
64    }
65}
66

C++ Solution

1#include <vector>
2#include <functional>
3#include <climits>
4using namespace std;
5
6class Solution {
7public:
8    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
9        // Calculate the number of vertices.
10        int numVertices = edges.size() + 1;
11        // Create an adjacency list for the graph.
12        vector<vector<int>> graph(numVertices);
13      
14        // Convert the edge list into an adjacency list.
15        for (const auto& edge : edges) {
16            int from = edge[0], to = edge[1];
17            graph[from].emplace_back(to);
18            graph[to].emplace_back(from);
19        }
20      
21        // Initialize the time-stamps vector with a default value of 'n' which is out of bounds.
22        vector<int> timestamps(numVertices, numVertices);
23      
24        // Depth-first search to update the timestamps at which each node can be visited when started from Bob's location.
25        function<bool(int, int, int)> dfsUpdateTimeStamps = [&](int vertex, int parent, int time) -> bool {
26            if (vertex == 0) {
27                timestamps[vertex] = time;
28                return true;
29            }
30            for (int neighbor : graph[vertex]) {
31                if (neighbor != parent && dfsUpdateTimeStamps(neighbor, vertex, time + 1)) {
32                    timestamps[neighbor] = min(timestamps[neighbor], time + 1);
33                    return true;
34                }
35            }
36            return false;
37        };
38      
39        // Run DFS from Bob's position to update the timestamps.
40        dfsUpdateTimeStamps(bob, -1, 0);
41        // Bob's position must have a timestamp of 0.
42        timestamps[bob] = 0;
43      
44        // Variable to store the answer - maximum profit.
45        int maximumProfit = INT_MIN;
46      
47        // Depth-first search to calculate the maximum possible profit while traversing the graph.
48        function<void(int, int, int, int)> dfsCalculateProfit = [&](int vertex, int parent, int time, int profit) {
49            // Increment the profit depending on the time relative to the timestamp.
50            if (time == timestamps[vertex])
51                profit += amount[vertex] / 2;
52            else if (time < timestamps[vertex])
53                profit += amount[vertex];
54          
55            // If it's a leaf node, update the maximum profit.
56            if (graph[vertex].size() == 1 && graph[vertex][0] == parent) {
57                maximumProfit = max(maximumProfit, profit);
58                return;
59            }
60          
61            // Continue DFS on adjacent nodes to explore further profit opportunities.
62            for (int neighbor : graph[vertex])
63                if (neighbor != parent) dfsCalculateProfit(neighbor, vertex, time + 1, profit);
64        };
65      
66        // Start DFS from vertex 0 to calculate the profit.
67        dfsCalculateProfit(0, -1, 0, 0);
68      
69        // Return the maximum calculated profit.
70        return maximumProfit;
71    }
72};
73

Typescript Solution

1// Import the necessary data structures from a library analogous to C++ STL
2import { max, min } from 'lodash';
3
4// Define the type for the graph edges and financial amounts
5type Edge = [number, number];
6type Graph = number[][];
7
8// Keep track of the number of vertices
9let numVertices: number;
10
11// Adjacency list for graph representation
12let graph: Graph;
13
14// Timstamps at which each node can be visited when started from Bob's location
15let timestamps: number[];
16
17// Global variable to store the maximum profit
18let maximumProfit: number = Number.MIN_SAFE_INTEGER;
19
20/**
21 * Converts the edge list into an adjacency list.
22 */
23function createGraph(edges: Edge[]): void {
24    numVertices = edges.length + 1;
25    graph = Array.from({ length: numVertices }, () => []);
26
27    for (const edge of edges) {
28        const [from, to] = edge;
29        graph[from].push(to);
30        graph[to].push(from);
31    }
32}
33
34/**
35 * Depth-first search to update the timestamps at which each node can be visited.
36 */
37function dfsUpdateTimeStamps(vertex: number, parent: number, time: number): boolean {
38    if (vertex === 0) {
39        timestamps[vertex] = time;
40        return true;
41    }
42    for (const neighbor of graph[vertex]) {
43        if (neighbor !== parent && dfsUpdateTimeStamps(neighbor, vertex, time + 1)) {
44            timestamps[neighbor] = min(timestamps[neighbor], time + 1);
45            return true;
46        }
47    }
48    return false;
49}
50
51/**
52 * Depth-first search to calculate the maximum possible profit while traversing the graph.
53 */
54function dfsCalculateProfit(vertex: number, parent: number, time: number, profit: number): void {
55    // Increment the profit depending on the time relative to the timestamp.
56    if (time === timestamps[vertex])
57        profit += Math.floor(amount[vertex] / 2);
58    else if (time < timestamps[vertex])
59        profit += amount[vertex];
60
61    // If it's a leaf node, update the maximum profit.
62    if (graph[vertex].length === 1 && graph[vertex][0] === parent) {
63        maximumProfit = max(maximumProfit, profit);
64        return;
65    }
66
67    // Continue DFS on adjacent nodes to explore further profit opportunities.
68    for (const neighbor of graph[vertex]) {
69        if (neighbor !== parent) dfsCalculateProfit(neighbor, vertex, time + 1, profit);
70    }
71}
72
73/**
74 * Initializes necessary variables and performs DFS to find the most profitable path.
75 */
76function mostProfitablePath(edges: Edge[], bob: number, amount: number[]): number {
77    timestamps = Array(numVertices).fill(numVertices);
78
79    // Create the graph based on edges
80    createGraph(edges);
81
82    // Run DFS from Bob's position to update the timestamps.
83    dfsUpdateTimeStamps(bob, -1, 0);
84    // Bob's position must have a timestamp of 0.
85    timestamps[bob] = 0;
86
87    // Start DFS from vertex 0 to calculate the profit.
88    dfsCalculateProfit(0, -1, 0, 0);
89
90    // Return the maximum calculated profit.
91    return maximumProfit;
92}
93

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be broken down into two main parts due to the depth-first search (DFS) operations – dfs1 and dfs2.

  1. dfs1: This function is a DFS that computes the minimum time ts[i] needed to reach node i from the node bob. It traverses each edge at most once as it searches for the path from bob to the root (node 0). Since the function ensures it does not traverse the same edge backward (by checking if j != fa), the time complexity for dfs1 is O(E), where E is the number of edges in the graph.

  2. dfs2: Similar to dfs1, this DFS traverses the graph to calculate the maximum profit path from the root (node 0) to a leaf. It takes into account the values ts[i] calculated in the first DFS to decide the profit gained from each node. The time complexity for this DFS is also O(E).

Given that these two DFS operations run sequentially, and each operates at O(E), the combined time complexity of the code is O(E + E), which simplifies to O(E).

Space Complexity

The space complexity of the code primarily arises from the space used to store the graph, the ts list, and the recursive stack used by the DFS functions.

  1. Graph representation (g): The graph is stored in an adjacency list representation using a defaultdict(list), which takes O(V + E) space, where V is the number of vertices and E is the number of edges (since each edge contributes to two entries in the adjacency list).

  2. The ts list: This is an array of size n, where n is the number of nodes in the graph. Hence, it takes O(n) space.

  3. DFS Recursion Stack: The recursion stack depth is limited by the maximum depth of the graph, which, in the worst case, can be O(n) (for a linked-list-like tree).

Combining these factors, the overall space complexity is O(V + E) + O(n) + O(n), which simplifies to O(n + E), as both V and n denote the number of vertices in the graph and V = n.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫