1997D - Maximize the Root - CodeForces Solution

def findval(vals,parents,childs,i,arr):
    l1 = [i]
    l2 = []
    while l1 != []:
        xx = l1.pop()
        l2.append(xx)
        for ii in childs[xx]:
            l1.append(ii)
    while l2 != []:
        xx = l2.pop()
        if childs[xx] == []:
            arr[xx] = vals[xx]
        else:
            minchildval = 1e9
            for j in childs[xx]:
                minchildval = min(minchildval,arr[j])
            if vals[xx] < minchildval:
                arr[xx] = (vals[xx]+minchildval)//2
            else:
                arr[xx] = minchildval
    return arr[i]

def findminvalfr(vals,parents,childs):
    x = 1e9
    arr = [-1 for i in range(len(vals))]
    for i in childs[0]:
        x = min(x,findval(vals,parents,childs,i,arr))
    return x

num = int(input())
out = []
for x in range(num):
    n = int(input())
    vals = [int(i) for i in input().split()]
    parents = [-1] + [int(i)-1 for i in input().split()]
    childs = []
    for i in range(n):
        childs.append([])
    for i in range(1,n):
        childs[parents[i]].append(i)
    if childs[0] == []:
        out.append(vals[0])
        continue
    minfr = findminvalfr(vals,parents,childs)
    out.append(vals[0]+minfr)

for i in out:
    print(int(i))