-
Notifications
You must be signed in to change notification settings - Fork 0
/
Most Profitable Path in a Tree
58 lines (53 loc) · 1.71 KB
/
Most Profitable Path in a Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
link - https://leetcode.com/problems/most-profitable-path-in-a-tree/
class Solution:
def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
n=len(amount)
adj=[[] for i in range(n)]
for u,v in edges:
adj[u].append(v)
adj[v].append(u)
def finpath(nod,vis,tem,bob):
tem.append(nod)
if nod==bob:
return True
for x in adj[nod]:
if x not in vis:
vis.add(x)
if finpath(x,vis,tem,bob) is True:
return True
vis.discard(x)
tem.pop(-1)
return False
tem=[]
finpath(0,set([0]),tem,bob)
midi=set()
bobi=set()
kk=len(tem)
if kk%2==1:
midi.add(tem[kk//2])
bobi=set(tem[kk//2+1:])
else:
bobi=set(tem[kk//2:])
total=[-1e12]
def maxprofit(nod,sumi,total,vis,bobi,midi):
flag=0
for x in adj[nod]:
if x not in vis:
vis.add(x)
tt=sumi
if x in midi:
tt=sumi+amount[x]//2
elif x not in bobi:
tt=sumi+amount[x]
flag=1
maxprofit(x,tt,total,vis,bobi,midi)
vis.discard(x)
if flag==0:
total[0]=max(total[0],sumi)
pp=0
if 0 in midi:
pp+=amount[0]//2
elif 0 not in bobi:
pp+=amount[0]
maxprofit(0,pp,total,set([0]),bobi,midi)
return total[0]