Учитывая n-арное дерево с N узлами, мы должны обработать Q запросов, где каждый запрос просит найти сумму всех узлов между любыми двумя заданными узлами (включая оба)
Пример:
1
/ \
2 3
/ \
4 5
Для (2,3) сумма = 2 + 1 + 3 = 6
Для (4,4) сумма = 4 + 2 + 1 + 3 = 10
My Подход: Поскольку это n-арное дерево, я рассматривал его как ациклический c граф. Для каждого запроса я использую алгоритм Дейкстры, чтобы найти путь между двумя заданными узлами, а затем вычисляю сумму всех узлов на этом пути. Но этот подход не имеет хорошей временной сложности, так как он является подходом с использованием грубой силы.
Сложность времени в подходе: O (QN log N)
Как мне подходить к проблеме для лучшей временной сложности?