Most Profitable Path in a Tree

Leetcode Problem:

• Most Profitable Path in a Tree

Summary

• The problem is to find the maximum net income that Alice can have if she travels towards the optimal leaf node in an undirected tree.

Approach

• The approach used is to use a depth-first search (DFS) traversal to find the optimal leaf node
• The DFS traversal is performed in two phases: first, to find the optimal leaf node for Bob, and second, to find the maximum net income for Alice
• The optimal leaf node for Bob is found by traversing the tree from node 0 and updating the amount array accordingly
• The maximum net income for Alice is then found by traversing the tree from the optimal leaf node and updating the sum variable accordingly.

Complexity

• O(n log n) due to the sorting of the amount array

Explanation

• The solution code first initializes the adjacency list and visited arrays
• It then defines two helper functions: goBobAndUpdateAmount and dfs
• The goBobAndUpdateAmount function performs the DFS traversal from node 0 to find the optimal leaf node for Bob, while the dfs function performs the DFS traversal from the optimal leaf node to find the maximum net income for Alice
• The solution code then calls the goBobAndUpdateAmount function to find the optimal leaf node for Bob, and then calls the dfs function to find the maximum net income for Alice
• The maximum net income for Alice is then returned as the result.

Solution Code:

class Solution {
    vector adj[100001];
    bool visited[100001] = {false,};
    bool visited2[100001] = {false,};
    bool isLeaf[100001] = {false,};
    int ans = -1000000001;
public:

    int goBobAndUpdateAmount(int node, int depth, int bob, vector& amount){
        if(visited[node]) return 100001;
        if(node == bob){
            amount[node] = 0;
            return depth;
        }
        visited[node] = true;
        int distanceBob = 100001;
        for(int i = 0 ; i < adj[node].size(); i++){
            int next = adj[node][i];
            distanceBob = goBobAndUpdateAmount(next, depth + 1, bob, amount);
            if(distanceBob == 100001) continue;
            if(depth > (distanceBob/2)){
                amount[node] = 0;
            } 
            if(depth == (distanceBob/2) && distanceBob %2 == 0){
                amount[node]/=2;
            }
            break;
        }
        return distanceBob;
    }
    void dfs(int node, int sum, vector& amount){
        if(visited2[node]) return;
        visited2[node] = true;
        sum += amount[node];
        if(isLeaf[node] && ans < sum){
            ans = sum;
        }
        for(int i = 0 ; i < adj[node].size(); i++){
            int next = adj[node][i];
            dfs(next, sum, amount);
        }
    }
    int mostProfitablePath(vector>& edges, int bob, vector& amount) {
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        for(int i = 1; i <= edges.size(); i++){
            if(adj[i].size() == 1) isLeaf[i] = true;
        }
        goBobAndUpdateAmount(0, 0, bob, amount);
        
        dfs(0, 0, amount);
        return ans;
    }
};