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

Question

我有一些 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) 中有效。但这对我来说太慢了。

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 同时进入两个可能的方向。让一个"pointer"到一个顶点（vl）朝一个方向移动，另一个（vr）朝另一个方向移动，并尽量保持从v到[=17的距离=] 尽可能接近从 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 当且仅当到 v 的右边在距离正好 i 那里是一个顶点，否则 a[i]=0
for 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 ...

对于另一个数组，数组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 序列的 convolution。（公式并不完全遵循定义，但很容易修改为确切的定义形式。）

所以我们现在需要的是给定a0和b0（我们可以在O(L)时间和space中计算），计算出S大批。在此之后，我们可以遍历 S 数组并简单地从 S[d]=2P+1.

中提取路径数

直接应用上面的公式就是O(L^2)。但是，两个序列的卷积can be calculated in O(L log L) by applying the Fast Fourier transform algorithm. Moreover, you can apply a similar Number theoretic transform（不知道有没有更好的link）只能用整数来避免精度问题。

所以算法的大纲就变成了

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' 是卷积本身。）

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

How to find all equals paths in degenerate tree, which start on specific vertex?

algorithm

graph

sum

doubly-linked-list