MorningBlues's blog

By MorningBlues, history, 3 years ago, In English

Hey guys can you please tell me what should be the time complexity of the following code for this problem. Shouldn't the complexity be O(n), n being the number of nodes? If this is O(n) why is it giving TLE??Is the base condition not correct?? (lru_cache is used for memoization)

from functools import lru_cache
import sys
sys.setrecursionlimit(2*10**5)
@lru_cache(None)
def solve(par,child,val):
    if len(g[child]) == 0:
        return 0
    if len(g[child])==1 and  g[child][0] == par:
        return 0 
    ans = 0 
    for x in g[child]:
        if x != par:
            #print(abs(val-arr[x-1][1]))
            ans = ans + max(solve(child,x,arr[x-1][0]) + abs(val-arr[x-1][0])  , solve( child, x,arr[x-1][1] ) +abs(val-arr[x-1][1]) )
        
    return ans
for _ in range(int(input())):
    from collections import defaultdict
    g = defaultdict(list)
    n = int(input())
    arr = []
    for _ in range(n):
        l,r = map(int,input().split(' '))
        arr.append([l,r])
    #print(arr)
    for _ in range(n-1):
        u,v = map(int,input().split(' '))
        g[u].append(v)
        g[v].append(u)
    #print(g)
    
    print(max(solve(-1,1,arr[0][0]) ,solve(-1,1,arr[0][1]) ) )
    solve.cache_clear()

  • Vote: I like it
  • -15
  • Vote: I do not like it

| Write comment?