2467: Most-Profitable-Path-in-a-Tree
Medium

table of contents

Initially, my solution involved 2 depth-first search runs; 1 to find the path between bob and 0 and 2 to find the maximum net income starting from 0. However, it is possible to merge both operations into 1 DFS run.

To do this, I first initialized an adjacencyMatrix, generated by iterating through all pairs, and created bob_distance to track the distance between each node and bob.

Then, we define a recursion function, dfs. This recursive function takes the current node, parent node, to prevent repeated traversal, and the depth of the current node (in relation to 0) and more previously defined variables. Using this,

Then, we first check if sum == INT32_MIN (as that means there are no children); if there is, then we set sum = 0.

Next, we check the depth of the current node, and compare it with the bob_distance[current] value:

Then, we can simply just return sum to return the maximum net income from a traversal to a leaf node.

code

class Solution {
public:
    int ans = -INT_MAX;
    vector<int> bob_distance;
    int dfs(int current, int parent, int depth, int bob, vector<vector<int>> &adjacencyMatrix, vector<int> &amount) {
        int sum = -INT_MAX;
        bob_distance[current] = ((current == bob) ? 0 : amount.size());

        for (int child : adjacencyMatrix[current]) {
            if (child != parent) {
                sum = max(sum, dfs(child, current, depth+1, bob, adjacencyMatrix, amount));
                bob_distance[current] = min(bob_distance[current], bob_distance[child]+1);
            }
        }
        if (sum == -INT_MAX) {
            sum = 0;
        }

        if (bob_distance[current] > depth) sum += amount[current];
        else if (bob_distance[current] == depth) sum += amount[current]/2;

        return sum;
    }
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        vector<vector<int>> adjacencyMatrix(edges.size()+1);    
        for (auto &pair : edges) {
            adjacencyMatrix[pair[0]].push_back(pair[1]);
            adjacencyMatrix[pair[1]].push_back(pair[0]);
        }
        bob_distance.resize(amount.size());
        
        return dfs(0, 0, 0, bob, adjacencyMatrix, amount);
    }
};

complexity