Будем говорить, что мы "входим в вершину", когда впервые заходим в нее dfs-ом, а "выходим из вершины", когда обошли всё ее поддерево (запустили dfs от всех ее детей), то есть закончили dfs в ней. Заметим, что если x родитель y, тогда сначала мы зайдем в x, потом зайдем в y, потом выйдем из y, потом выйдем из x. Только в таком порядке, потому что y (вместе со своим поддеревом) лежит в поддереве x. Если же ни x ни y не является родителем другого, тогда мы сначала обойдем поддерево одного, потом другого, те: зайдем в x, выйдем из x, зайдем в y, выйдем из y.

Получается, что для того чтобы проверять, является ли x родителем y, нам достаточно знать порядок входов и выходов в x и y.

Для того чтобы быстро проверять этот порядок, давайте во время обхода dfs-ом для каждой вершины сохранять, каким по счету было это событие входа или выхода. Это называется время входа (tin) и время выхода (tout).

Тогда на запрос можно будет ответить за О(1) -- x родитель y, если tin[x] < tin[y] and tout[y] < tout[x].

Пример кода на python:
def dfs(h):
    global time
    tin[h] = time
    time += 1
    for e in g[h]:
        dfs(e)
    tout[h] = time
    time += 1


n = int(input())
g = [[] for i in range(n)] #set чтобы убрать повторы
inp = list(map(int, input().split()))
for i in range(n):
    if inp[i] == 0:
        continue
    g[inp[i] - 1].append(i)
tin = [0] * n
tout = [0] * n
time = 0
for i in range(n):
    if inp[i] == 0: #запускаемся из корней
        dfs(i)
m = int(input())
for i in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if tin[x] < tin[y] and tout[y] < tout[x]:
        print(1)
    else:
        print(0)