> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.
> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.
# Most Profitable Path in a Tree Python Solution
> Tested Python solution for LeetCode 2467 with 20 pytest cases. Generate a practice environment with lcpy.
LeetCode 2467, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Tree](/catalog/topics/tree), [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Graph Theory](/catalog/topics/graph-theory). [View on LeetCode](https://leetcode.com/problems/most-profitable-path-in-a-tree/description/).
Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:
```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2467 # by problem number
lcpy gen -s most_profitable_path_in_a_tree # by problem name
```
## Problem
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.
### Examples
```
Input: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
Output: 6
```
```
Input: edges = [[0,1]], bob = 1, amount = [-7280,2350]
Output: -7280
```
### Constraints
* 2 \<= n \<= 10\5\
* edges.length == n - 1
* edges\[i].length == 2
* 0 \<= a\i\, b\i\ \< n
* a\i\ != b\i\
* edges represents a valid tree.
* 1 \<= bob \< n
* amount.length == n
* amount\[i] is an even integer in the range \[-10\4\, 10\4\].
## Solution
Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/most_profitable_path_in_a_tree/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/most_profitable_path_in_a_tree/test_solution.py):
```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
# Time: O(n)
# Space: O(n)
def most_profitable_path(self, edges: list[list[int]], bob: int, amount: list[int]) -> int:
n = len(amount)
adj: list[list[int]] = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
depth = [0] * n
parent = [-1] * n
order = [0]
for u in order:
for v in adj[u]:
if v != parent[u]:
parent[v] = u
depth[v] = depth[u] + 1
order.append(v)
bob_time: dict[int, int] = {}
node, t = bob, 0
while True:
bob_time[node] = t
if node == 0:
break
node = parent[node]
t += 1
gain = [0] * n
for u in reversed(order):
child_best = max((gain[v] for v in adj[u] if v != parent[u]), default=0)
gate = amount[u]
bt = bob_time.get(u, -1)
if bt == -1 or bt > depth[u]:
pass
elif bt == depth[u]:
gate = amount[u] // 2
else:
gate = 0
gain[u] = gate + child_best
return gain[0]
```
## Complexity
| Time | Space |
| - | - |
| O(n) | O(n) |
## Tags
[NeetCode All](/catalog/neetcode).
This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.