Определение наличия узла X в поддереве другого узла Y или наоборот для запросов Q

Опубликовано: 19 Сентября, 2022

Дано дерево с N узлами и (N-1) ребрами, а исходный узел находится на 1- й позиции . Имеется Q запросов, каждый из которых имеет тип {pos, X, Y} . Выполните следующую операцию в зависимости от типа запроса:

  • Если pos = 0 , то найдите, присутствует ли Y в поддереве X.
  • Если pos = 1 , то найдите, присутствует ли X в поддереве Y.

Примеры:

Input: N: = 9, edges = {{1, 2}, {1, 3}, {2, 6}, {2, 7}, {6, 9}, {7, 8}, {3, 4}, {3, 5}}
Q = 5, query = {{0, 2, 8}, {1, 2, 8}, {1, 6, 5}, {0, 6, 5}, {1, 9, 1}}
Output: {Yes, No, No, No, Yes}
Explanation: See the image below. 
8 is present in the subtree of 2 and 9 is also present in the subtree of 9.
For the other queries it does not satisfy the condition.

Input: N = 2, edges = {{1, 2}}
Q = 1, query = {0, 2, 1}
Output: {No}
Explanation: 1 is not present in the subtree of 2.

Подход: Решение задачи основано на DFS. Учитывайте время входа и выхода для каждого узла. Используя это, можно легко проверить, присутствует ли какой-либо узел в поддереве другого узла или нет. Выполните шаги, указанные ниже:

  • Сначала найдите время (время, когда мы входим в этот узел) и время выхода (время, когда мы покидаем этот узел) для каждого из узлов (изначально наш таймер равен 1), используя обход дерева DFS .
  • Затем для каждого из запросов в соответствии с его типом найдите , присутствует ли Y в поддереве X или наоборот.
  • Чтобы проверить, присутствует ли Y в поддереве X , проверьте, больше ли время Y, чем X , а время выхода Y меньше, чем X , и наоборот, чтобы проверить, присутствует ли X в поддереве Y.

Ниже приведена реализация описанного выше подхода.


Временная сложность: O(max (N, Q))
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ