Facebook Pixel

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.

Flowchart Walkthrough

Here's an analysis based on the Flowchart for elucidating the appropriate algorithm in solving Leetcode 2467. Most Profitable Path in a Tree:

Is it a graph?

  • Yes: The problem description suggests that we are dealing with a graphical representation where nodes (cities) are connected by edges (roads).

Is it a tree?

  • Yes: From the problem statement, it's clear that we are dealing with a tree structure (no cycles, and every two nodes are connected by exactly one path).

Is the problem related to directed acyclic graphs (DAGs)?

  • No: Although a tree is a special form of DAG, the problem focus isn't specifically about DAG functionalities such as topological sorting.

Is the problem related to shortest paths?

  • No: The goal is to find the most profitable path, which while similar to shortest path algorithms in strategy, distinctly focuses on maximizing profit rather than minimizing distance or cost.

Conclusion: The flowchart leads us to utilize DFS (Depth-First Search) which is suitable for tree-based problems where we are dealing with maximizing or minimizing certain criteria along paths, like profit in this case.

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.

Learn more about Tree, Depth-First Search, Breadth-First Search and Graph patterns.

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

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

Now, let's walk through the solution steps:

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

    g = {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.

    ts = [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:

    After 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.

Solution Implementation

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
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
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
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