I attempted the LCA question on SPOJ and I have tried to implement LCA using RMQ but I end up getting Runtime Errors. The answers are correct for my custom test cases and the default testcases. Can anyone help me out?
My implementation:
from collections import defaultdict
from math import log2
lookup = [[0 for i in range(100001)] for j in range(20)]
euler = []
visited = [0 for i in range(100001)]
depth = [0 for i in range(100001)]
depth_euler = []
fai = [10**10 for i in range(100001)]
def preprocess(depthArr,n):
global lookup
for i in range(n):
lookup[i][0] = i
j = 1
while (1 << j) <= n:
i = 0
while i + (1 << j) - 1 < n:
if (depthArr[lookup[i][j - 1]] < depthArr[lookup[i + (1 << (j - 1))][j - 1]]):
lookup[i][j] = lookup[i][j - 1]
else:
lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1]
i += 1
j += 1
def query(arr, L, R):
global lookup
j = int(log2(R - L + 1))
if (arr[lookup[L][j]] <=
arr[lookup[R - (1 << j) + 1][j]]):
return lookup[L][j]
else:
return lookup[R - (1 << j) + 1][j]
def dfs(graph,node,level):
global visited
global euler
global depth_euler
global fai
visited[node] = 1
depth[node] = level
euler.append(node)
depth_euler.append(level)
fai[node] = min(len(euler),fai[node])
flag = 0
for ele in graph[node]:
if(visited[ele] == 0):
flag = 1
dfs(graph,ele,level+1)
euler.append(node)
depth_euler.append(level)
for _ in range(int(input())):
n = int(input())
graph = defaultdict(list)
lookup = [[0 for i in range(19)] for j in range(100001)]
euler = []
visited = [0 for i in range(100001)]
depth = [0 for i in range(100001)]
depth_euler = []
fai = [10**10 for i in range(100001)]
for i in range(n):
line = list(map(int,input().split()))
graph[i+1] = line[1:]
for ele in line[1:]:
graph[ele].append(i+1)
dfs(graph,1,0)
preprocess(depth_euler,len(depth_euler))
# print(fai)
# print(euler)
# print(depth_euler)
q = int(input())
for i in range(q):
line = list(map(int,input().split()))
if(line[0]==line[1]):
print(line[0])
continue
elif(fai[line[0]]>fai[line[1]]):
line = line[::-1]
print(euler[query(depth_euler,fai[line[0]],fai[line[1]])])