aboutsummaryrefslogtreecommitdiff
path: root/most_profitable_path_tree.py
diff options
context:
space:
mode:
Diffstat (limited to 'most_profitable_path_tree.py')
-rw-r--r--most_profitable_path_tree.py58
1 files changed, 58 insertions, 0 deletions
diff --git a/most_profitable_path_tree.py b/most_profitable_path_tree.py
new file mode 100644
index 0000000..c419a13
--- /dev/null
+++ b/most_profitable_path_tree.py
@@ -0,0 +1,58 @@
+# 2467. Most Profitable Path in a Tree
+
+"""
+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] = [a_i, b_i]' indicates that there is an edge between nodes 'a_i'
+and 'b_i' 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 case
+reward obtained on oening the gate at node 'i' otherwise. return the maximum
+net income alice can have if she travels towards the optimal leaf node.
+"""
+
+
+class Solution(object):
+ def mostProfitablePath(self, edges, bob, amount):
+ """
+ :type edges: List[List[int]]
+ :type bob: int
+ :type amount: List[int]
+ :rtype: int
+ """
+ n = len(edges) + 1
+ graph = [[] for i in range(n)]
+ vis = [0] * n
+ for i, j in edges:
+ graph[i].append(j)
+ graph[j].append(i)
+
+ def dfs(i, v):
+ vis[i] = 1
+ res = -float("inf")
+ db = 0 if i == bob else n
+ for j in graph[i]:
+ if vis[j]:
+ continue
+ cur, kk = dfs(j, v + 1)
+ res = max(res, cur)
+ db = min(db, kk)
+ if res == -float("inf"):
+ res = 0
+ if v == db:
+ res += amount[i] // 2
+ if v < db:
+ res += amount[i]
+ return res, db + 1
+
+ return dfs(0, 0)[0]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.mostProfitablePath(
+ edges=[[0, 1], [1, 2], [1, 3], [3, 4]], bob=3, amount=[-2, 4, 2, -4, 6]
+ )
+ )
+ print(obj.mostProfitablePath(edges=[[0, 1]], bob=1, amount=[-7280, 2350]))