algorithm - 如何在退化树中找到所有从特定顶点开始的均等路径？

Question

我有一些degenerate tree(看起来像数组或双向链表)。例如，这棵树:

每个边缘都有一定的重量。我想找到从每个顶点开始的所有相等路径。

换句话说，我想获取所有元组(v1，v，v2)，其中v1和v2是任意祖先和后代，即c(v1, v) = c(v, v2)。

让边缘具有以下权重(仅作为示例):
a-b = 3b-c = 1c-d = 1d-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)中工作。但这对我来说太慢了。

Answer 1

您在评论中写道，当前的方法是

It seems, I looking for a way to decrease constant in O(n^2). I choose some vertex. Then I create two set. Then I fill these sets with partial sums, while iterating from this vertex to start of tree and to finish of tree. Then I find set intersection and get number of paths from this vertex. Then I repeat algorithm for all other vertices.

在所谓的两个指针方法的基础上，有一种更简单，更快速的 O(n^2)方法。

对于每个顶点， 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)

(通过预先计算前缀和，您可以在O(1)中找到 dist。)

很容易看出，只要您没有零长度的边，就不会错过相等的对。

关于更快的解决方案，如果要列出所有对，则不能更快地列出，因为在最坏的情况下，对的数量为O(n ^ 2)。但是，如果仅需要这些对的数量，则可能存在更快的算法。

UPD :我想出了另一种算法来计算数量，如果您的边缘很短，可能会更快。如果将链的总长度(所有边的权重之和)表示为 L，则算法以 O(L log L)运行。但是，它在概念上要先进得多，编码也要先进得多。

首先是一些理论上的推理。考虑一些顶点 v。让我们有两个数组， a和 b，不是C样式的零索引数组，而是索引从 -L到 L的数组。

让我们定义

表示i>0，a[i]=1 iff在v右边的距离上，恰好是i是一个顶点，否则为a[i]=0

表示i=0，a[i]≡a[0]=1

表示i<0，a[i]=1 iff在v的左侧，距离上-i正好有一个顶点，否则a[i]=0

对该数组的简单理解如下。拉伸(stretch)图形并将其沿坐标轴放置，以使每个边的长度等于其权重，并且顶点 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 ...  

对于另一个数组 b数组，我们相对于原点以对称方式定义值，就好像我们已经反转了轴的方向一样:

表示i>0，b[i]=1 iff在v左侧，恰好距离i是一个顶点，否则为b[i]=0

代表i=0，b[i]≡b[0]=1

表示i<0，b[i]=1 iff在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)，它们仅反射(reflect)正数位置，还有一个位置 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]

很明显，如果您还记得带有沿坐标轴拉伸(stretch)的树的图片。

现在让我们考虑另一个数组 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序列中的 convolution。 (该公式并不完全符合定义，但是很容易修改为确切的定义形式。)

因此，我们现在需要的是 a0和 b0(可以在 O(L)的时间和空间中进行计算)，然后计算 S数组。之后，我们可以遍历 S数组，并简单地从 S[d]=2P+1提取路径数。

上面公式的直接应用是 O(L^2)。但是，通过应用快速傅立叶变换算法对两个序列 can be calculated in O(L log L) 进行卷积。此外，您可以应用类似的 Number theoretic transform(不知道是否有更好的链接)仅与整数一起使用，并避免精度问题。

因此，该算法的总体轮廓变为

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'是适合的卷积。)