у меня есть немногоdegenerate tree (выглядит как массив или двусвязный список). Например, вот это дерево:

Каждый край имеет некоторый вес. Я хочу найти все равные пути, которые начинаются в каждой вершине.

Другими словами, я хочу получить все кортежи (v1, v, v2), где v1 и v2 - произвольные предки и потомки, так чтоc(v1, v) = c(v, v2).

Пусть ребра имеют следующие веса (это просто пример):

a-b = 3

b-c = 1

c-d = 1

d-e = 1

Затем:

ВершинаA не имеет равного пути (нет вершины с левой стороны).ВершинаB имеет одну равную пару. ПутьB-A равняется путиB-E (3 == 3).ВершинаC имеет одну равную пару. ПутьB-C равняется путиC-D (1 == 1).ВершинаD имеет одну равную пару. ПутьC-D равняется путиD-E (1 == 1).ВершинаE не имеет равного пути (нет вершины с правой стороны).

Я реализую простой алгоритм, который работает вO(n^2), Но это слишком медленно для меня.