Найдите, является ли длина пути четной или нечетной между заданными узлами дерева для запросов Q

Для общего дерева, состоящего из N узлов и (N – 1) ребер, и массива запросов query[] размера Q , состоящего из типа {A, B} , задача для каждого запроса состоит в том, чтобы проверить, соответствует ли длина пути между двумя заданные узлы A и B четны или нечетны.

Примеры:

Input: query[] = {{2, 4}, {4, 0}}

Output:
Odd
Even
Explanation:
For the 1st query A = 2 and B = 4. The path from A to B is 2 -> 0 -> 1 -> 3 -> 4 having a length of 5 i.e., Odd.
For the 2nd query A = 4 and B = 0. The path from A to B is 4 -> 3 -> 1 -> 0 having a length of 4 i.e., Even.

Подход: Данная проблема может быть эффективно решена путем преобразования дерева в двудольный граф. Можно заметить, что если данные вершины A и B в запросе находятся на одной стороне построенного двудольного графа, то длина пути между A и B должна быть нечетной, а если A и B находятся на разных сторонах, то путь длина должна быть нечетной. Ниже приведены шаги, которые необходимо выполнить:

• Пройдите по данному дереву, используя BFS Traversal.
• Разделите все узлы на 2 набора так, чтобы все два соседних узла в дереве находились в разных наборах (т. е. 0 или 1 ). Для этого назначьте переменный номер набора каждому уровню во время обхода BFS, назначив заданное количество текущих узлов = 1 XOR номер родителя текущего узла .
• После выполнения вышеуказанных шагов пройдите по заданному массиву запросов query[] и, если установленное количество обоих узлов одинаково, длина пути от A до B равна Odd . В противном случае это Even .

Ниже приведена реализация вышеуказанного подхода:

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