There is an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0. You are given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
At every node i, there is a gate. You are also given an array of even integers amount, where amount[i] represents:
the price needed to open the gate at node i, if amount[i] is negative, or,
the cash reward obtained on opening the gate at node i, otherwise.
The game goes on as follows:
Initially, Alice is at node 0 and Bob is at node bob.
At every second, Alice and Bob each move to an adjacent node. Alice moves towards some leaf node, while Bob moves towards node 0.
For every node along their path, Alice and Bob either spend money to open the gate at that node, or accept the reward. Note that:
If the gate is already open, no price will be required, nor will there be any cash reward.
If Alice and Bob reach the node simultaneously, they share the price/reward for opening the gate there. In other words, if the price to open the gate is c, then both Alice and Bob pay c / 2 each. Similarly, if the reward at the gate is c, both of them receive c / 2 each.
If Alice reaches a leaf node, she stops moving. Similarly, if Bob reaches node 0, he stops moving. Note that these events are independent of each other.
Return the maximum net income Alice can have if she travels towards the optimal leaf node._
Input: edges =[[0,1],[1,2],[1,3],[3,4]], bob =3, amount =[-2,4,2,-4,6]Output: 6Explanation:
The above diagram represents the given tree. The game goes as follows:- Alice is initially on node 0, Bob on node 3. They open the gates of their respective nodes. Alice's net income is now -2.- Both Alice and Bob move to node 1. Since they reach here simultaneously, they open the gate together and share the reward. Alice's net income becomes -2+(4/2)=0.- Alice moves on to node 3. Since Bob already opened its gate, Alice's income remains unchanged. Bob moves on to node 0, and stops moving.- Alice moves on to node 4 and opens the gate there. Her net income becomes 0+6=6.Now, neither Alice nor Bob can make any further moves, and the game ends.It is not possible for Alice to get a higher net income.
Input: edges =[[0,1]], bob =1, amount =[-7280,2350]Output: -7280Explanation:
Alice follows the path 0->1 whereas Bob follows the path 1->0.Thus, Alice opens the gate at node 0 only. Hence, her net income is-7280.
Constraints:
2 <= n <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges represents a valid tree.
1 <= bob < n
amount.length == n
amount[i] is an even integer in the range [-104, 104].
To solve the problem of determining Alice’s maximum profit while considering Bob’s movement, we used a two-step Depth-First Search (DFS) approach. Here’s the detailed explanation:
The interaction between Alice and Bob at each node depends on their relative arrival times. Hence, precomputing when Bob arrives at each node (bobTime) simplifies the calculations during Alice’s traversal.
Alice’s traversal ensures all paths to every leaf node are explored, guaranteeing that the optimal path is found.
classSolution {
// Represents the tree as an adjacency listprivate List<List<Integer>> tree;
// Tracks when Bob reaches each nodeprivate Map<Integer, Integer> bobTime;
// Tracks visited nodes during DFSprivateboolean[] visited;
// Stores the profit or loss at each nodeprivateint[] amount;
// Stores the maximum income Alice can achieveprivateint maxIncome = Integer.MIN_VALUE;
publicintmostProfitablePath(int[][] edges, int bob, int[] amount) {
int n = amount.length;
// Initialize adjacency list for the tree tree =new ArrayList<>();
for (int i = 0; i < n; i++) {
tree.add(new ArrayList<>());
}
// Build the tree from the provided edgesfor (int[] edge : edges) {
tree.get(edge[0]).add(edge[1]); // Add edge in both directions tree.get(edge[1]).add(edge[0]);
}
// Initialize bobTime map and visited array bobTime =new HashMap<>();
visited =newboolean[n];
// Perform DFS to calculate Bob's arrival times dfsBob(bob, 0);
// Store the `amount` array for Alice's traversalthis.amount= amount;
// Reset visited array for Alice's DFS Arrays.fill(visited, false);
// Perform DFS for Alice's traversal, starting from the root (node 0) dfsAlice(0, 0, 0);
// Return the maximum income Alice can achievereturn maxIncome;
}
// DFS to calculate when Bob reaches each nodeprivatebooleandfsBob(int node, int time) {
bobTime.put(node, time); // Record the time Bob reaches this node visited[node]=true; // Mark node as visited// If Bob reaches the root, we are doneif (node == 0) {
returntrue;
}
// Explore neighbours recursivelyfor (int nei : tree.get(node)) {
if (!visited[nei]) { // Only visit unvisited nodesif (dfsBob(nei, time + 1)) { // Recur for connected nodesreturntrue; // If root is reached, stop recursion }
}
}
// If path to root doesn't exist through this node, remove it from bobTime bobTime.remove(node);
returnfalse;
}
// DFS to calculate Alice's maximum incomeprivatevoiddfsAlice(int node, int time, int income) {
visited[node]=true; // Mark node as visited// Update income based on Alice and Bob's arrival timesif (!bobTime.containsKey(node) || time < bobTime.get(node)) {
// If Alice reaches first or Bob never visits the node income += amount[node];
} elseif (time == bobTime.get(node)) {
// If Alice and Bob arrive simultaneously, they share the amount income += amount[node]/ 2;
}
// If Alice reaches a leaf node, update the maximum incomeif (tree.get(node).size() == 1 && node != 0) { // Skip root as leaf node maxIncome = Math.max(maxIncome, income);
}
// Recur for all unvisited neighboursfor (int nei : tree.get(node)) {
if (!visited[nei]) {
dfsAlice(nei, time + 1, income); // Recur for next node }
}
}
}
classSolution:
defmostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
n = len(amount) # Number of nodes tree = [[] for _ in range(n)] # Adjacency list representation of the tree# Build the adjacency listfor a, b in edges:
tree[a].append(b)
tree[b].append(a)
bobTime = {} # Stores the time Bob reaches each node visited = [False] * n # Tracks visited nodes for DFS maxIncome = float('-inf') # Stores the maximum income Alice can achieve# Nested function for Bob's DFSdefdfsBob(node: int, time: int) -> bool:
nonlocal bobTime
bobTime[node] = time # Record Bob's arrival time visited[node] =True# Mark node as visitedif node ==0: # If Bob reaches the root, stopreturnTruefor nei in tree[node]:
ifnot visited[nei]: # Traverse unvisited neighboursif dfsBob(nei, time +1):
returnTrue bobTime.pop(node) # Remove node if it doesn't lead to the rootreturnFalse# Nested function for Alice's DFSdefdfsAlice(node: int, time: int, income: int):
nonlocal maxIncome
visited[node] =True# Mark node as visited# Calculate Alice's income based on interaction with Bobif node notin bobTime or time < bobTime[node]:
income += amount[node] # Alice reaches firstelif time == bobTime[node]:
income += amount[node] //2# Alice and Bob arrive simultaneously# Update maximum income if node is a leafif len(tree[node]) ==1and node !=0: # Leaf node check maxIncome = max(maxIncome, income)
for nei in tree[node]:
ifnot visited[nei]: # Traverse unvisited neighbours dfsAlice(nei, time +1, income)
# Perform DFS for Bob starting at `bob` dfsBob(bob, 0)
# Reset visited array for Alice's traversal visited = [False] * n
# Perform DFS for Alice starting at the root (node 0) dfsAlice(0, 0, 0)
return maxIncome