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

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

然后:

1. 顶点A没有任何相等的路径(左侧没有顶点).
2. 顶点B有一对相等.路径B-A等于路径B-E (3 == 3).
3. 顶点C有一对相等.路径B-C等于路径C-D (1 == 1).
4. 顶点D有一对相等.路径C-D等于路径D-E (1 == 1).
5. 顶点E没有任何相等的路径(右侧没有顶点).

我实现了简单的算法,它适用于O(n^2).但对我来说这太慢了.

Answer 1

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

\n\n

\n

看来，我正在寻找一种减少 O(n^2) 常数的方法。我选择一些顶点。然后我创建了两组。然后，我用部分和来填充这些集合，同时从该顶点迭代到树的开头和树的结尾。然后我找到集合交集并获取来自该顶点的路径数。然后我对所有其他顶点重复该算法。

\n

\n\n

我认为有一种更简单、更快的O(n^2)方法，基于所谓的两指针方法。

\n\n

对于每个顶点，v同时进入两个可能的方向。让一个“指针”指向vl朝一个方向移动的顶点 ( )，另一个“指针vr”指向另一个方向，并尝试使 到 的距离尽可能接近从v到的距离。每次这些距离变得相等时，您就有相等的路径。vlvvr

\n\n

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

\n\n

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

\n\n

很容易看出，只要没有零长度的边，就不会丢失任何相等的对。

\n\n

关于更快的解决方案，如果你想列出所有对，那么你不能做得更快，因为在最坏的情况下对的数量将是 O(n^2)。但如果您只需要这些对的数量，可能存在更快的算法。

\n\n

UPD：我想出了另一种计算金额的算法，如果你的边缘相当短，它可能会更快。如果将链的总长度（所有边权重的总和）表示为L，则算法的运行时间为O(L log L)。然而，它在概念上更先进，在编码上也更先进。

\n\n

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

\n\n

让我们定义

\n\n

\n
• 对于i>0，当a[i]=1且仅当在距离的右侧恰好有一个顶点，否则via[i]=0
\n
• 为了i=0，a[i]\xe2\x89\xa1a[0]=1
\n
• 对于i<0，当a[i]=1且仅当在距离的左侧恰好存在一个顶点，否则v-ia[i]=0
\n

\n\n

这个数组的简单理解如下。拉伸图形并将其沿坐标轴放置，使每条边的长度等于其重量，并且该顶点v位于原点。然后当a[i]=1且仅当在坐标 处有一个顶点i。

\n\n

对于您的示例和顶点“b”选择为v：

\n\n

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

\n\n

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

\n\n

\n
• 对于i>0，当b[i]=1且仅当在距离的左侧恰好有一个顶点，否则vib[i]=0
\n
• 为了i=0，b[i]\xe2\x89\xa1b[0]=1
\n
• 对于i<0，当b[i]=1且仅当在距离的右侧恰好存在一个顶点，否则v-ib[i]=0
\n

\n\n

现在考虑第三个数组，c其中c[i]=a[i]*b[i]星号保留用于普通乘法。显然，当且仅当到左侧c[i]=1的长度路径在一个顶点处结束，并且到右侧abs(i)的长度路径在一个顶点处结束。abs(i)因此，i>0其中的每个位置c都c[i]=1对应于您需要的路径。还有负位置（c[i]=1with i<0），它只反映正位置，还有一种位置where c[i]=1，即position i=0。

\n\n

计算 中所有元素的总和c。这个总和将为sum(c)=2P+1，其中P是您需要的以其中心为中心的路径总数v。所以如果你知道的话sum(c)，你就可以很容易地确定P。

\n\n

现在让我们更仔细地考虑数组a以及b当我们更改顶点时它们如何变化v。让我们表示v0最左边的顶点（树的根）以及a0该顶点b0对应的a和数组。b

\n\n

对于任意顶点v表示d=dist(v0,v)。然后很容易看出，对于顶点，v数组a和b只是数组a0并b0移动了d：

\n\n

a[i]=a0[i+d]\nb[i]=b0[i-d]\n

\n\n

如果您还记得树沿坐标轴拉伸的图片，那就很明显了。

\n\n

现在让我们考虑另一个数组S（一个数组代表所有顶点），对于每个顶点，v让我们将 的值放入元素sum(c)中S[d]（d并且c取决于v）。

\n\n

更准确地说，让我们定义数组，S以便对于每个d

\n\n

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

\n\n

一旦我们知道了S数组，我们就可以迭代顶点，并为每个顶点简单地v 获取它，因为对于每个顶点我们有sum(c)S[d]d=dist(v,v0)vsum(c)=sum(a0[i+d]*b0[i-d])。

\n\n

但公式S很简单：S就是和的卷积a0b0。（该公式并不完全遵循定义，但很容易修改为精确的定义形式。）

\n\n

所以我们现在需要的是给定a0and b0（我们可以在O(L)时间和空间上计算），计算S数组。之后，我们可以迭代S数组并简单地从中提取路径数S[d]=2P+1。

\n\n

直接应用上面的公式就是O(L^2)。然而，两个序列的卷积可以通过应用快速傅立叶变换算法来计算。O(L log L)此外，您可以应用类似的数论变换（不知道是否有更好的链接）来仅处理整数并避免精度问题。

\n\n

所以算法的总体轮廓就变成了

\n\n

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

\n\n

（我之所以这样称呼它，是corrected_convolution因为S它并不完全是一个卷积，而是一个非常相似的对象，可以应用类似的算法。此外，你甚至可以定义S\'[2*d]=S[d]=sum(a0[i+d]*b0[i-d])=sum(a0[i]*b0[i-2*d])，然后S\'就是卷积本身。）

\n