Most Profitable Path in a Tree

class ProfitablePathCalc {
public:
    int optimalPathProfit(vector<vector<int>>& connections, int bobLoc,
                          vector<int>& profits) {
        nodeCount = profits.size();
        adjacencyList.resize(nodeCount, vector<int>());

        // Building the adjacency list
        for (vector<int> connection : connections) {
            adjacencyList[connection[0]].push_back(connection[1]);
            adjacencyList[connection[1]].push_back(connection[0]);
        }
        bobDistance.resize(nodeCount);
        return calculateProfit(0, -1, 0, bobLoc, profits);
    }

private:
    vector<vector<int>> adjacencyList;
    vector<int> bobDistance;
    int nodeCount;

    // DFS to determine maximum potential profit
    int calculateProfit(int node, int parent, int duration, int bobLoc,
                        vector<int>& profits) {
        int maximumProfit = 0, highestChildProfit = INT_MIN;

        // Setting nodes' distances relative to Bob's location
        if (node == bobLoc)
            bobDistance[node] = 0;
        else
            bobDistance[node] = nodeCount;
        for (int neighbor : adjacencyList[node]) {
            if (neighbor != parent) {
                highestChildProfit = max(highestChildProfit, calculateProfit(neighbor, node,
                                                    duration + 1, bobLoc, profits));
                bobDistance[node] =
                    min(bobDistance[node],
                        bobDistance[neighbor] + 1);
            }
        }
        // Check if only Alice (not Bob) has reached the node
        if (bobDistance[node] > duration) maximumProfit += profits[node];

        // Check if both Alice and Bob reach the node simultaneously
        else if (bobDistance[node] == duration)
            maximumProfit += profits[node] / 2;

        // Include child node profits for the total profit
        if (highestChildProfit == INT_MIN)
            return maximumProfit;
        else
            return maximumProfit + highestChildProfit;
    }
};

class Solution {

    public int maximumProfitFromPath(int[][] connections, int bobLocation, int[] profits) {
        int verticesCount = profits.length;
        var graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < verticesCount; i++) {
            graph.add(new ArrayList<>());
        }
        int[] distances = new int[verticesCount];

        // Construct the graph from connections
        for (int[] connection : connections) {
            graph.get(connection[0]).add(connection[1]);
            graph.get(connection[1]).add(connection[0]);
        }

        return calculateMaxProfit(0, 0, 0, bobLocation, profits);
    }

    private ArrayList<ArrayList<Integer>> graph;
    private int[] distances;
    private int totalVertices;

    // Recursive DFS function to compute the profit
    private int calculateMaxProfit(
        int currentNode,
        int parent,
        int currentTime,
        int bobLocation,
        int[] profits
    ) {
        int bestProfit = 0, maxSubtreeProfit = Integer.MIN_VALUE;

        // Initialize distances from Bob's location
        if (currentNode == bobLocation) {
            distances[currentNode] = 0;
        } else {
            distances[currentNode] = totalVertices;
        }

        for (int neighbor : graph.get(currentNode)) {
            if (neighbor != parent) {
                int childProfit = calculateMaxProfit(neighbor, currentNode, currentTime + 1, bobLocation, profits);
                maxSubtreeProfit = Math.max(maxSubtreeProfit, childProfit);
                distances[currentNode] = Math.min(distances[currentNode], distances[neighbor] + 1);
            }
        }

        // Condition when Alice gets to the node first
        if (distances[currentNode] > currentTime) {
            bestProfit += profits[currentNode];
        }
        // Condition when both reach at the same time
        else if (distances[currentNode] == currentTime) {
            bestProfit += profits[currentNode] / 2;
        }

        // Determine the profit to return, considering child nodes
        return (maxSubtreeProfit == Integer.MIN_VALUE) ? bestProfit : bestProfit + maxSubtreeProfit;
    }
}

class ProfitCalculator:
    def __init__(self):
        self.graph = []
        self.bob_dist = []
        self.total_nodes = 0

    def optimalPathValue(self, connections, bob_location, profits):
        self.total_nodes = len(profits)
        self.graph = [[] for _ in range(self.total_nodes)]
        self.bob_dist = [0] * self.total_nodes

        # Establish graph with connections
        for conn in connections:
            self.graph[conn[0]].append(conn[1])
            self.graph[conn[1]].append(conn[0])

        return self.calculateProfit(0, 0, 0, bob_location, profits)

    # Perform Depth-first Search
    def calculateProfit(self, node, parent, steps, bob_location, profits):
        highest_profit = 0
        deepest_profit = float("-inf")

        # Set distance from Bob
        if node == bob_location:
            self.bob_dist[node] = 0
        else:
            self.bob_dist[node] = self.total_nodes

        for neighbor in self.graph[node]:
            if neighbor != parent:
                deepest_profit = max(
                    deepest_profit,
                    self.calculateProfit(neighbor, node, steps + 1, bob_location, profits),
                )
                self.bob_dist[node] = min(
                    self.bob_dist[node],
                    self.bob_dist[neighbor] + 1,
                )

        # Consider profits depending on reach times
        if self.bob_dist[node] > steps:
            highest_profit += profits[node]
        elif self.bob_dist[node] == steps:
            highest_profit += profits[node] // 2

        # Collect total profits including children nodes
        return highest_profit if deepest_profit == float("-inf") else highest_profit + deepest_profit