Как найти в вырожденном дереве все равные пути, начинающиеся с определенной вершины?

Вы пишете в комментариях, что ваш текущий подход

Кажется, я искал способ уменьшить константу в O (n ^ 2). Выбираю какую-нибудь вершину. Затем создаю два комплекта. Затем я заполняю эти множества частичными суммами, выполняя итерацию от этой вершины до начала дерева и до конца дерева. Затем я нахожу пересечение множества и получаю количество путей из этой вершины. Затем повторяю алгоритм для всех остальных вершин.

Есть более простой и, я думаю, более быстрый O(n^2) подход, основанный на так называемом методе двух указателей.

Для каждого vertix v идите одновременно в двух возможных направлениях. Имейте один «указатель» на вершину (vl), движущуюся в одном направлении, а другой (vr) в другом направлении, и постарайтесь сохранить расстояние от v до vl как можно ближе к расстоянию от v до vr. Каждый раз, когда эти расстояния становятся равными, у вас есть равные пути.

for v in vertices
    vl = prev(v)
    vr = next(v)
    while (vl is still inside the tree) 
              and (vr is still inside the tree)
        if dist(v,vl) < dist(v,vr)
            vl = prev(vl)
        else if dist(v,vr) < dist(v,vl)
            vr = next(vr)
        else // dist(v,vr) == dist(v,vl)
            ans = ans + 1
            vl = prev(vl)
            vr = next(vr)

(Предварительно вычислив суммы префиксов, вы можете найти dist в O (1).)

Легко видеть, что никакая равная пара не будет пропущена при условии, что у вас нет ребер нулевой длины.

Что касается более быстрого решения, если вы хотите перечислить все пары, вы не можете сделать это быстрее, потому что количество пар будет O (n ^ 2) в худшем случае. Но если вам нужно только количество этих пар, могут существовать более быстрые алгоритмы.

UPD: я придумал другой алгоритм для расчета суммы, который может быть быстрее, если ваши края довольно короткие. Если вы обозначите общую длину вашей цепочки (сумму веса всех ребер) как L, то алгоритм будет работать в O(L log L). Однако он намного более продвинут в концептуальном плане и более продвинут в кодировании.

Во-первых, некоторые теоретические рассуждения. Рассмотрим некоторую вершину v. Пусть у нас есть два массива, a и b, не массивы с нулевым индексом в стиле C, а массивы с индексацией от -L до L.

Определим

• для i>0, a[i]=1 если вправо от v на расстоянии ровно i есть вершина, в противном случае a[i]=0
• для i=0, a[i]≡a[0]=1
• для i<0, a[i]=1 если слева от v на расстоянии ровно -i есть вершина, в противном случае a[i]=0

Простое понимание этого массива заключается в следующем. Растяните график и положите его вдоль оси координат так, чтобы длина каждого ребра равнялась его весу, а вершина v лежала в начале координат. Тогда a[i]=1, если есть вершина в координате i.

Для вашего примера и для вершины "b", выбранной как v:

          a--------b--c--d--e
     --|--|--|--|--|--|--|--|--|-->
      -4 -3 -2 -1  0  1  2  3  4
a: ... 0  1  0  0  1  1  1  1  0 ...  

Для другого массива, array b, мы определяем значения симметрично относительно начала координат, как если бы мы инвертировали направление оси:

• для i>0, b[i]=1 если слева от v на расстоянии ровно i есть вершина, в противном случае b[i]=0
• для i=0, b[i]≡b[0]=1
• для i<0, b[i]=1, если вправо от v на расстоянии ровно -i есть вершина, в противном случае b[i]=0

Теперь рассмотрим третий массив c такой, что c[i]=a[i]*b[i] звездочка здесь остается для обычного умножения. Очевидно c[i]=1, если и только если путь длиной abs(i) влево заканчивается вершиной, а путь длиной abs(i) вправо заканчивается вершиной. Таким образом, для i>0 каждая позиция в c, имеющая c[i]=1, соответствует нужному вам пути. Есть также отрицательные позиции (c[i]=1 с i<0), которые просто отражают положительные позиции, и еще одна позиция, где c[i]=1, а именно позиция i=0.

Вычислите сумму всех элементов в c. Эта сумма будет равна sum(c)=2P+1, где P - общее количество необходимых вам путей, а v будет его центром. Так что, если вы знаете sum(c), вы легко можете определить P.

Давайте теперь более внимательно рассмотрим массивы a и b и то, как они меняются, когда мы меняем вершину v. Обозначим v0 крайнюю левую вершину (корень вашего дерева) и a0 и b0 соответствующие массивы a и b для этой вершины.

Для произвольной вершины v обозначим d=dist(v0,v). Тогда легко увидеть, что для вершины v массивы a и b - это просто массивы a0 и b0, сдвинутые на d:

a[i]=a0[i+d]
b[i]=b0[i-d]

Это очевидно, если вспомнить картинку с растянутым по координатной оси деревом.

Теперь давайте рассмотрим еще один массив, S (один массив для всех вершин), и для каждой вершины v поместим значение sum(c) в элемент S[d] (d и c зависят от v).

Точнее, определим массив S так, чтобы для каждого d

S[d] = sum_over_i(a0[i+d]*b0[i-d])

Как только мы узнаем массив S, мы можем перебирать вершины и для каждой вершины v получить его sum(c) просто как S[d] с d=dist(v,v0), потому что для каждой вершины v у нас есть sum(c)=sum(a0[i+d]*b0[i-d]).

Но формула для S очень проста: S - это просто свертка a0 и b0 последовательности. (Формула не совсем соответствует определению, но ее легко преобразовать в точную форму определения.)

Итак, что нам сейчас нужно, это даны a0 и b0 (которые мы можем вычислить в O(L) времени и пространстве), вычислить массив S. После этого мы можем перебрать массив S и просто извлечь номера путей из S[d]=2P+1.

Прямое применение приведенной выше формулы - O(L^2). Однако свертка двух последовательностей может быть вычислена в O(L log L) с помощью алгоритма быстрого преобразования Фурье. . Более того, вы можете применить аналогичное теоретико-числовое преобразование (не знаю, есть ли лучшая ссылка ), чтобы работать только с целыми числами и избежать проблем с точностью.

Таким образом, общая схема алгоритма становится

calculate a0 and b0   // O(L)
calculate S = corrected_convolution(a0, b0)    // O(L log L)
v0 = leftmost vertex (root)
for v in vertices:
    d = dist(v0, v)
    ans = ans + (S[d]-1)/2

(Я называю это corrected_convolution, потому что S не совсем свертка, а очень похожий объект, для которого можно применить аналогичный алгоритм. Более того, вы даже можете определить S'[2*d]=S[d]=sum(a0[i+d]*b0[i-d])=sum(a0[i]*b0[i-2*d]), и тогда S' является собственно сверткой.)