题目描述

blablabla

python非递归写法（递归爆栈）

from collections import deque
m,n=map(int,input().split())
order=list(map(int,input().split()))
pre=list(map(int,input().split()))

dic={}
q=deque([[0,n-1,0,n-1,0,float("inf")]])
while q:
    pl,pr,dl,dr,d,f=q.popleft()
    root=pre[pl]
    dic[root]=[f,d]
    k=order.index(root)
    if dl<k:
        q.append([pl+1,pl+1+(k-1-dl),dl,k-1,d+1,root])
    if k<dr:
        q.append([pl+1+(k-1-dl)+1,pr,k+1,dr,d+1,root])


for _ in range(m):
    a,b=map(int,input().split())
    if a not in dic and b not in dic:
        print("ERROR: {} and {} are not found.".format(a,b))
    elif a not in dic:
        print("ERROR: {} is not found.".format(a))
    elif b not in dic:
        print("ERROR: {} is not found.".format(b))
    else:
        fa=a
        fb=b
        da=dic[a][1]
        db=dic[b][1]
        while fa!=fb:
            if da<db:
                fb=dic[fb][0]
                db-=1
            else:
                fa=dic[fa][0]
                da-=1
        if fa==a:
            print("{} is an ancestor of {}.".format(a,b))
        elif fa==b:
            print("{} is an ancestor of {}.".format(b,a))
        else:
            print("LCA of {} and {} is {}.".format(a,b,fa))