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

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-AB-E。
顶点有一对相等的顶点。路径(3 == 3)等于路径CB-C。
顶点有一对相等的顶点。路径C-D等于路径(1 == 1)D。
顶点C-D没有任何相等的路径（右侧没有顶点）。
我实现了简单算法，它在D-E中工作。但对我来说太慢了。

Answer 1

你在评论中写道，你目前的做法是
看来，我在寻找一种降低o（n^2）常数的方法。我选择
一些顶点。然后我创建两个集合。然后我把这些装满
部分和，同时从这个顶点迭代到树的开始和
完成树。然后我找到集合交集，得到路径数
从这个顶点。然后对所有其他顶点重复算法。
基于所谓的双指针方法，有一种更简单、更快的O(n^2)方法。
对于每个垂直方向，同时进入两个可能的方向。让一个指向顶点（v）的“指针”在一个方向上移动，另一个（vl）在另一个方向上移动，并尽量使从vr到v的距离尽可能接近从vl到v的距离。每次这些距离相等，你就有相等的路径。

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）中找到 vr。）
很容易看出，如果没有零长度的边，就不会遗漏相等的对。
关于更快的解决方案，如果要列出所有对，则不能更快地列出，因为在最坏的情况下，对的数量将为o（n^2）。但是，如果只需要这些对的数量，就可能存在更快的算法。
upd：我想出了另一种算法来计算数量，如果你的边比较短的话，这个算法可能会更快。如果将链的总长度（所有边的权重之和）表示为 dist，则算法将在 L中运行。然而，它在概念上更先进，在编码上也更先进。
首先是一些理论推理。考虑一些顶点 O(L log L)。让我们有两个数组， v和 a，它们不是c风格的零索引数组，而是索引从 b到 -L的数组。
让我们来定义
对于 L， i>0iff在 a[i]=1右边的距离正好 v。
是顶点，否则 i
对于 a[i]=0， i=0
对于 a[i]≡a[0]=1， i<0iff在 a[i]=1左边的距离上正好有一个顶点，否则 v
对这个数组的简单理解如下。伸展你的图形并沿着坐标轴放置它，使每个边的长度等于它的重量，而顶点 -i位于原点。如果坐标 a[i]=0处有一个顶点。
对于您的示例和选择为 v的顶点“b”：

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

对于另一个数组，数组 a[i]=1，我们以原点对称的方式定义值，好像我们已经反转了轴的方向：
对于 i， viff在 b的左边
是顶点，否则 i>0
对于 b[i]=1， v
对于 i， b[i]=0iff在 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：

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

很明显，如果你记得树沿着坐标轴伸展的图片。
现在让我们再考虑一个数组， a0（所有顶点使用一个数组），对于每个顶点，让我们将 b0的值放入 a元素（ b和 v取决于 d=dist(v0,v)）。
更准确地说，让我们定义数组 v以便对每个 a

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

一旦我们知道 b数组，我们就可以在顶点上迭代，对于每个顶点 a0只需使用 b0就可以得到它的 d，因为对于每个顶点 S我们都有 v。
但是 sum(c)的公式非常简单： S[d]只是 d和 c序列的 convolution。（公式不完全遵循定义，但很容易修改为精确的定义形式。）
所以我们现在需要的是 v和 S（我们可以在 d时间和空间中计算），计算 S数组。在此之后，我们可以迭代 v数组并简单地从 sum(c)中提取路径数。
上述公式的直接应用是 S[d]。但是，应用快速傅立叶变换算法，两个序列的卷积 can be calculated in d=dist(v,v0)。此外，您可以应用类似的 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

（我称之为 v，因为 sum(c)=sum(a0[i+d]*b0[i-d])并不完全是一个卷积，而是一个非常相似的对象，可以应用类似的算法。此外，您甚至可以定义 S，然后 S是正确的卷积。）