1941. Предок

Напишите программу, которая для двух вершин дерева определяет, является ли одна из них предком другой.

Вход. Первая строка содержит количество вершин в дереве n (1 ≤ n ≤ 10⁵). Во второй строке находится n чисел, i-ое из которых определяет номер непосредственного родителя вершины с номером i. Если это число равно нулю, то вершина является корнем дерева.

В третьей строке находится количество запросов m (1 ≤ m ≤ 10⁵). Каждая из следующих m строк содержит два различных числа a и b (1 ≤ a, b ≤ n).

Выход. Для каждого из m запросов выведите в отдельной строке число 1, если вершина a является одним из предков вершины b, и 0 в противном случае.

Пример входа	Пример выхода
6 0 1 1 2 3 3 5 4 1 1 4 3 6 2 6 6 5	0 1 1 0 0

РЕШЕНИЕ

графы – поиск в глубину

Анализ алгоритма

Дерево будем хранить в виде ориентированного графа, в котором ребра идут от предков к сыновьям (для экономии памяти). Реализуем на нем поиск в глубину, расставив для каждой вершины v метки d[v] и f[v]. Вершина a является одним из предков вершины b, если d[a] < d[b] < f[b] < f[a]. Это означает, что интервал [d[b]; f[b]] должен включаться в интервал [d[a]; f[a]].

Но поскольку для каждой вершины b всегда выполняется неравенство d[b] < f[b], то для каждой входной пары вершин (запроса) a и b достаточно проверить неравенства d[a] < d[b] и f[b] < f[a].

Пример

Граф, приведенный в примере, с расстановками меток имеет следующий вид:

Например, 1 является предком 5, так как d[1] < d[5] и f[5] < f[1]. Действительно, интервал [7; 8] включается в [1; 12].

Реализация алгоритма

Поскольку количество вершин в графе велико, будем хранить граф в виде списка смежности g. Массив used используется для отмечания уже пройденных вершин. Метки времени входа и выхода из вершины будем хранить в массивах d и f.

vector<vector<int> > g;

vector<int> used, d, f;

Запускаем процедуру поиска в глубину dfs. Расставляем метки d[v] и f[v].

void dfs(int v)

{

used[v] = 1; d[v] = time++;

for(int i = 0; i < g[v].size(); i++)

{

int to = g[v][i];

if (!used[to]) dfs(to);

}

f[v] = time++;

}

Функция is_Parent возвращает 1, если a является предком b, и 0 иначе. Проверяем выполнение двух неравенств d[a] < d[b] и f[b] < f[a].

int is_Parent(int a, int b)

{

return (d[a] < d[b]) && (f[b] < f[a]);

}

Основная часть программы. Читаем входной граф. Если вершина a является родителем вершины i, то добавим в граф ориентированное ребро (a, i) (для экономии памяти можно воспользоваться ориентированным графом). Вершины графа нумеруются числами от 1 до n. Если a = 0, то вершина i является корнем, в этом случае никакого ребра добавлять не надо. В переменной root ищем номер вершины – корня дерева.

scanf("%d",&n);

g.resize(n+1); used.resize(n+1);

d.resize(n+1); f.resize(n+1);

for(i = 1; i <= n; i++)

{

scanf("%d",&a);

if(!a) root = i; else g[a].push_back(i);

}

Запускаем поиск в глубину из корня дерева root.

dfs(root);

Читаем запросы и выводим ответ на каждый из них за константное время.

scanf("%d",&m);

for(i = 0; i < m; i++)

{

scanf("%d %d",&a,&b);

printf("%d\n",is_Parent(a,b));

}