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()