2467. Most Profitable Path in a Tree
Explanation:
To solve this problem, we can perform a depth-first search (DFS) on the tree starting from node 0. During the DFS, we keep track of the total income Alice can achieve by reaching each node. At each node, we calculate the maximum net income Alice can have by considering the gate at the current node and the gates at its children.
We need to handle the case where Alice and Bob reach the same node at the same time. In this case, they share the price/reward equally.
After the DFS, we return the maximum net income Alice can achieve by reaching a leaf node.
Time Complexity: The time complexity of this approach is O(N), where N is the number of nodes in the tree.
Space Complexity: The space complexity of this approach is O(N) for the recursive stack.
:
class Solution {
public int[] dfs(int node, int parent, List<Integer>[] adjList, int[] amount, int bob) {
int[] income = new int[2]; // income[0] for Alice, income[1] for Bob
for (int child : adjList[node]) {
if (child == parent) continue;
int[] childIncome = dfs(child, node, adjList, amount, bob);
income[0] += Math.max(childIncome[0] + Math.max(amount[node] / 2, 0), childIncome[1] + amount[node]);
income[1] += Math.max(childIncome[1] + Math.max(amount[node] / 2, 0), childIncome[0] + amount[node]);
}
return income;
}
public int mostProfitablePath(int n, int[][] edges, int bob, int[] amount) {
List<Integer>[] adjList = new ArrayList[n];
for (int i = 0; i < n; i++) {
adjList[i] = new ArrayList<>();
}
for (int[] edge : edges) {
adjList[edge[0]].add(edge[1]);
adjList[edge[1]].add(edge[0]);
}
int[] result = dfs(0, -1, adjList, amount, bob);
return result[0];
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.