Company Queries II

n,q = [int(x) for x in input().split()]

d_ancestor = [int(x) for x in input().split()]
k=2
ancestors = []
ancestors.append([0,0]+d_ancestor)
flag = True

depth = [0,0]
for i in range(2,n+1):
    depth.append(depth[d_ancestor[i-2]]+1)

while flag:
    L=[]
    flag = False
    for i in range(n+1):
        anc = ancestors[-1][ancestors[-1][i]]
        L.append(ancestors[-1][ancestors[-1][i]])
        if anc !=0:
            flag = True
    ancestors.append(L)

def ancestor(node,depth):
    c_node  = node
    
    for index,val in enumerate(bin(depth)[:1:-1]):
        if val =="1":
            c_node = ancestors[index][c_node]

    return c_node

for querie in range(q) :
    a,b = [int(x) for x in input().split()]
    if a == 1 or b == 1:
        print(1)

    else:
        diff_depth = depth[a]-depth[b]        
        if diff_depth!=0:
            if diff_depth<0:
                b = ancestor(b,-diff_depth)
            else :
                a = ancestor(a,diff_depth)
        if a == b:
            print(a)
        else:
            anc_a = d_ancestor[a-2] 
            anc_b = d_ancestor[b-2] 
            while anc_a != anc_b:
                anc_a = d_ancestor[anc_a-2] 
                anc_b = d_ancestor[anc_b-2]
            print(anc_a)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED