Most Profitable Path in a Tree | Leetcode 2467

class Solution {
    bool findBobPath(vector<vector<int>>& adj,int bob,int parent,vector<int>& curr_path,vector<int>& bob_path){
        if(bob==0){
            bob_path = curr_path;
            return true;
        }
        //Traverse all nbrs
        curr_path.push_back(bob);
        for(int nbr: adj[bob]){
            if(nbr!=parent and findBobPath(adj,nbr,bob,curr_path,bob_path))
                return true;
        }
        curr_path.pop_back();
        return false;
    }
    int findMaxIncomeForAlice(vector<vector<int>>& adj,int alice,int parent,vector<int>& amount){
        int max_income = INT_MIN;
        for(int nbr: adj[alice]){
            if(nbr!=parent){
                int income = findMaxIncomeForAlice(adj,nbr,alice,amount);
                if(income + amount[alice] > max_income)
                    max_income = income + amount[alice];
            }
        }
        return max_income==INT_MIN?amount[alice]:max_income;
    }
public:
    int mostProfitablePath(vector<vector<int>>& edges, int bob,vector<int>& amount) {
        //Step-1: Make Adj List
        int n=amount.size();
        vector<vector<int>> adj(n);
        for(auto edge: edges){
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        //Step-2: Find the Bob to root path
        vector<int> curr_path,bob_path;
        findBobPath(adj,bob,-1,curr_path,bob_path);

        //Step-3: Update amount of half of the path nodes to 0
        int size = bob_path.size();
        int i;
        for(i=0;i<size/2;++i)
            amount[bob_path[i]]=0;
        
        if(size&1)  amount[bob_path[i]]=0;
        else        amount[bob_path[i]]/=2;//Half contribution for common meeting point

        //Step-4: Apply DFS to find the max sum
        return findMaxIncomeForAlice(adj,0,-1,amount);
    }
};
/*
//JAVA
import java.util.*;

class Solution {
    private boolean findBobPath(List<List<Integer>> adj, int bob, int parent, List<Integer> currPath, List<Integer> bobPath) {
        if (bob == 0) {
            bobPath.addAll(currPath);
            return true;
        }
        currPath.add(bob);
        for (int nbr : adj.get(bob)) {
            if (nbr != parent && findBobPath(adj, nbr, bob, currPath, bobPath)) {
                return true;
            }
        }
        currPath.remove(currPath.size() - 1);
        return false;
    }

    private int findMaxIncomeForAlice(List<List<Integer>> adj, int alice, int parent, int[] amount) {
        int maxIncome = Integer.MIN_VALUE;
        for (int nbr : adj.get(alice)) {
            if (nbr != parent) {
                int income = findMaxIncomeForAlice(adj, nbr, alice, amount);
                if (income + amount[alice] > maxIncome) {
                    maxIncome = income + amount[alice];
                }
            }
        }
        return maxIncome == Integer.MIN_VALUE ? amount[alice] : maxIncome;
    }

    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        int n = amount.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        List<Integer> currPath = new ArrayList<>();
        List<Integer> bobPath = new ArrayList<>();
        findBobPath(adj, bob, -1, currPath, bobPath);

        int size = bobPath.size();
        int i;
        for (i = 0; i < size / 2; ++i) {
            amount[bobPath.get(i)] = 0;
        }
        if (size % 2 == 1) {
            amount[bobPath.get(i)] = 0;
        } else {
            amount[bobPath.get(i)] /= 2;
        }

        return findMaxIncomeForAlice(adj, 0, -1, amount);
    }
}

#Python
from typing import List

class Solution:
    def findBobPath(self, adj: List[List[int]], bob: int, parent: int, curr_path: List[int], bob_path: List[int]) -> bool:
        if bob == 0:
            bob_path.extend(curr_path)
            return True
        curr_path.append(bob)
        for nbr in adj[bob]:
            if nbr != parent and self.findBobPath(adj, nbr, bob, curr_path, bob_path):
                return True
        curr_path.pop()
        return False

    def findMaxIncomeForAlice(self, adj: List[List[int]], alice: int, parent: int, amount: List[int]) -> int:
        max_income = float('-inf')
        for nbr in adj[alice]:
            if nbr != parent:
                income = self.findMaxIncomeForAlice(adj, nbr, alice, amount)
                if income + amount[alice] > max_income:
                    max_income = income + amount[alice]
        return max_income if max_income != float('-inf') else amount[alice]

    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        n = len(amount)
        adj = [[] for _ in range(n)]
        for edge in edges:
            adj[edge[0]].append(edge[1])
            adj[edge[1]].append(edge[0])

        curr_path, bob_path = [], []
        self.findBobPath(adj, bob, -1, curr_path, bob_path)

        size = len(bob_path)
        i = 0
        for i in range(size // 2):
            amount[bob_path[i]] = 0
        if size % 2 == 1:
            amount[bob_path[i]] = 0
        else:
            amount[bob_path[i]] //= 2

        return self.findMaxIncomeForAlice(adj, 0, -1, amount)

*/