Most Profitable Path in a Tree

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,

we initialize sum = INT32_MIN, to keep track of the maximum possible sum of the node & all its children, and set bob_distance[current] equal to 0 or the number of nodes in the tree (depending on if current == bob)

since we do not care about bob_distance[current] if current is not in the path between 0 and bob, it means we can auto-initialize bob_distance to the number of nodes in the tree it will always be greater than the depth of any node

then, we can iterate through all its children (that are not equal to its parent) to find which child has the maximum sum value, and to determine the minimum bob_distance[current]

we find this maximum sum value by running dfs on all its children through sum = max(sum, dfs(...))

then, we find the minimum bob_distance[current] by checking all the bob_distance[child]+1 and seeing if they are smaller than the current bob_distance[current]

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:

depth < bob_distance[current], we know that this node is closer to 0 than to bob, so sum += amount[current]

depth == bob_distance[current], we know that this node is equidistant to 0 and bob, so sum += amount[current]/2

depth > bob_distance[current], we know that this node is closer to bob than to 0, so sum += 0

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

Time: O(n)

Space: O(n)