如何找到所有等于堕落的树路径，它开始在特定的顶点？ [英] How to find all equals paths in degenerate tree, which start on specific vertex?

问题描述

我有一些堕落的树（它看起来像为数组或双向链表）。例如，它是这样的树：

I have some degenerate tree (it looks like as array or doubly linked list). For example, it is this tree:

每个边缘有一定的权重。我想找到人人平等的路径，它开始在每个顶点。

Each edge has some weight. I want to find all equal paths, which starts in each vertex.

换句话说，我想获得的所有元组（V1，V，V2），其中V1和V2是任意的祖先和后代，这样 C（V1，V）= C（V，V2 ）。

In other words, I want to get all tuples (v1, v, v2) where v1 and v2 are an arbitrary ancestor and descendant such that c(v1, v) = c(v, v2).

让边缘有以下的权重（这只是举例）：

Let edges have the following weights (it is just example):

A-B = 3

B-C = 1

C-D = 1

D-E = 1

然后：

1. 顶点 A 没有任何平等的路径（没有从左边顶点）。
2. 顶点 B 有一个平等的对。路径 BA 等于到路径为 （3 == 3）。
3. 顶点 C 有一个平等的对。路径 BC 等于到路径光盘 （1 == 1）。
4. 顶点 D 有一个平等的对。路径光盘等于到路径 DE （1 == 1）。
5. 顶点电子没有任何平等的路径（没有从右侧顶点）。

1. The vertex A does not have any equal path (there is no vertex from left side).
2. The vertex B has one equal pair. The path B-A equals to the path B-E (3 == 3).
3. The vertex C has one equal pair. The path B-C equals to the path C-D (1 == 1).
4. The vertex D has one equal pair. The path C-D equals to the path D-E (1 == 1).
5. The vertex E does not have any equal path (there is no vertex from right side).

我实现简单的算法，在它的工作原理为O（n ^ 2）。但是，对我来说太缓慢。

I implement simple algorithm, which works in O(n^2). But it is too slow for me.

推荐答案

您写的评论，你目前的做法是

You write, in comments, that your current approach is

看来，我在寻找一种方式来减少常数为O（n ^ 2）。我选   一些顶点。然后，我创建了两个集。然后我填补这些套与   部分款项，而从这个顶点迭代开始树和   完成树。然后我找到交集，并得到路径数   从这个顶点。然后，我再说一遍算法，把所有其他顶点。

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）办法的基础上，所谓的两个指针的方法。

There is a simpler and, I think, faster O(n^2) approach, based on the so called two pointers method.

对于每个vertix v 走在同一时间为两个可能的方向。有一个指针到顶点（ VL ）朝着一个方向，另一个（ VR ）到另一个方向，和v尽量保持距离的距离为V 到 VL 尽量靠近距离 到 VR 越好。每当这些距离相等，你有相同的路径。

For each vertix v go at the same time into two possible directions. Have one "pointer" to a vertex (vl) moving in one direction and another (vr) into another direction, and try to keep the distance from v to vl as close to the distance from v to vr as possible. Each time these distances become equal, you have equal paths.

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)

（由precalculating的preFIX款项，你可以找到 DIST 在O（1）。）

可以很容易地看到，没有平等对将被错过，只要你没有零长度的边缘。

It's easy to see that no equal pair will be missed provided that you do not have zero-length edges.

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

Regarding a faster solution, if you want to list all pairs, then you can't do it faster, because the number of pairs will be O(n^2) in the worst case. But if you need only the amount of these pairs, there might exist faster algorithms.

UPD ：我想出了另一种算法计算的量的，这可能是在情况下更快的边缘相当短。如果你表示你的链的总长度（各边权重之和）为→，然后在的算法运行Ø（L日志L）。然而，这是更先进的概念和更先进的编码了。

UPD: I came up with another algorithm for calculating the amount, which might be faster in case your edges are rather short. If you denote the total length of your chain (sum of all edges weight) as L, then the algorithm runs in O(L log L). However, it is much more advanced conceptually and more advanced in coding too.

一是一些理论推理。考虑到一些顶点 v 。我们有两个数组， A 和 B ，而不是C风格的零索引的数组，但数组与指数化从 -L 到→。

Firstly some theoretical reasoning. Consider some vertex v. Let us have two arrays, a and b, not the C-style zero-indexed arrays, but arrays with indexation from -L to L.

让我们定义

• 为 I＆GT; 0 ， A [1] = 1 当且仅当给的右键的 v 上的距离正好我有 是一个顶点，否则 A [1] = 0
• 为 I = 0 ， A [1]≡a[0] = 1
• 为 I＆LT; 0 ， A [1] = 1 当且仅当给的离开的 v 上的距离正好 -i 有一个顶点，否则 A [I ] = 0

• for i>0, a[i]=1 iff to the right of v on the distance exactly i there is a vertex, otherwise a[i]=0
• for i=0, a[i]≡a[0]=1
• for i<0, a[i]=1 iff to the left of v on the distance exactly -i there is a vertex, otherwise a[i]=0

这个数组的一个简单理解如下。伸展你的图形，并奠定其沿坐标轴，使每个边具有的长度等于它的重量，而且顶点 v 在于原点。然后 A [1] = 1 当且仅当有一个顶点坐标为我。

A simple understanding of this array is as follows. Stretch your graph and lay it along the coordinate axis so that each edge has the length equal to its weight, and that vertex v lies in the origin. Then a[i]=1 iff there is a vertex at coordinate i.

有关你的榜样，为顶点的B选为 v ：

For your example and for vertex "b" chosen as 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 ，我们定义一个对称的方式中的值相对于原点，仿佛我们已经倒轴的方向：

For another array, array b, we define the values in a symmetrical way with respect to origin, as if we have inverted the direction of the axis:

• 为 I＆GT; 0 ， B [I] = 1 当且仅当给的离开的 v 上的距离正好我有 是一个顶点，否则 B [I] = 0
• 为 I = 0 ， B [I]≡b[0] = 1
• 为 I＆LT; 0 ， B [I] = 1 当且仅当给的右键的 v 上的距离正好 -i 有一个顶点，否则 B [我] = 0

• for i>0, b[i]=1 iff to the left of v on the distance exactly i there is a vertex, otherwise b[i]=0
• for i=0, b[i]≡b[0]=1
• for i<0, b[i]=1 iff to the right of v on the distance exactly -i there is a vertex, otherwise b[i]=0

现在考虑第三阵列 C ，使得 C [I] = A [1] * B [I] ，星号在这里停留普通乘法。显然 C [I] = 1 当且仅当长的路 ABS（我）在顶点的左侧末端，和长度 ABS（我）到正确的路径顶点结束。因此，对于 I＆GT; 0 C 已在每个位置 C [I] = 1 对应你所需要的路径。也有消极的位置（ C [I] = 1 与 I＆LT; 0 ），这正好反映了积极立场，还有一位置 C [I] = 1 ，即位置 I = 0 。

Now consider a third array c such that c[i]=a[i]*b[i], asterisk here stays for ordinary multiplication. Obviously c[i]=1 iff the path of length abs(i) to the left ends in a vertex, and the path of length abs(i) to the right ends in a vertex. So for i>0 each position in c that has c[i]=1 corresponds to the path you need. There are also negative positions (c[i]=1 with i<0), which just reflect the positive positions, and one more position where c[i]=1, namely position i=0.

计算所有元素的 C 的总和。这笔款项将和（C）= 2P + 1 ，其中 P 是您需要的路径总数与 v 是它的中心。所以，如果你知道和（C），你可以很容易地确定 P 。

Calculate the sum of all elements in c. This sum will be sum(c)=2P+1, where P is the total number of paths which you need with v being its center. So if you know sum(c), you can easily determine P.

现在让我们考虑更紧密阵列 A 和 B 以及当我们改变顶点<？他们改变code> v 。让我们表示 V0 最左边的顶点（你的树的根）和 A0 和 B0 相应的 A 和 B 数组顶点。

Let us now consider more closely arrays a and b and how do they change when we change the vertex v. Let us denote v0 the leftmost vertex (the root of your tree) and a0 and b0 the corresponding a and b arrays for that vertex.

有关任意顶点 v 分别表示 D = DIST（V0，V）。那么很容易地看到，顶点 v 阵列 A 和 B 只是数组 A0 和 B0 按ð：

For arbitrary vertex v denote d=dist(v0,v). Then it is easy to see that for vertex v the arrays a and b are just arrays a0 and b0 shifted by d:

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

如果你还记得的画面，沿坐标轴伸树这是显而易见的。

It is obvious if you remember the picture with the tree stretched along a coordinate axis.

现在，让我们考虑一个阵列，取值（一个阵列的所有顶点），并为每个顶点 v 让我们把和（C）到 S [D]。元素（ð和 C 依赖于 v ）。

Now let us consider one more array, S (one array for all vertices), and for each vertex v let us put the value of sum(c) into the S[d] element (d and c depend on v).

更多precisely，让我们定义阵列取值，以便为每个 D

More precisely, let us define array S so that for each d

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

一旦我们知道了取值阵列，我们可以遍历顶点，每个顶点 v 获得了和（C）简单地 S [D]。与 D = DIST（V，V0），因为每个顶点 v 我们和（C）= SUM（A0 [I + D] * B0 [ID ]）。

Once we know the S array, we can iterate over vertices and for each vertex v obtain its sum(c) simply as S[d] with d=dist(v,v0), because for each vertex v we have sum(c)=sum(a0[i+d]*b0[i-d]).

不过，公式取值很简单：取值正好的卷积的 A0 和 B0 序列。 （该公式不会精确地跟随定义，但很容易修改的确切定义表格。）

But the formula for S is very simple: S is just the convolution of the a0 and b0 sequences. (The formula does not exactly follow the definition, but is easy to modify to the exact definition form.)

所以，我们现在需要的是给定的 A0 和 B0 （我们可以在 O（L）时间和空间），计算出取值阵列。在此之后，我们就可以遍历取值阵列和简单地从 S [D]。= 2P + 1 。

So what we now need is given a0 and b0 (which we can calculate in O(L) time and space), calculate the S array. After this, we can iterate over S array and simply extract the numbers of paths from S[d]=2P+1.

公式直接应用上面 O（L ^ 2）。然而，两个序列的卷积可以在计算 0（L日志L） 通过应用快速傅立叶变换算法。此外，你可以申请一个类似数论变换（不知道是否有更好的联系）仅与整数工作，避免precision问题。

Direct application of the formula above is O(L^2). However, the convolution of two sequences can be calculated in O(L log L) by applying the Fast Fourier transform algorithm. Moreover, you can apply a similar Number theoretic transform (don't know whether there is a better link) to work with integers only and avoid precision problems.

因此​​该算法的一般轮廓变得

So the general outline of the algorithm becomes

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'[2 * D] = S [D]。= SUM（A0 [I + D] * B0 [ID]）= SUM（A0 [我] * B0 [I-2 * D]），然后 S'是卷积正确的。）

(I call it corrected_convolution because S is not exactly a convolution, but a very similar object for which a similar algorithm can be applied. Moreover, you can even define S'[2*d]=S[d]=sum(a0[i+d]*b0[i-d])=sum(a0[i]*b0[i-2*d]), and then S' is the convolution proper.)

这篇关于如何找到所有等于堕落的树路径，它开始在特定的顶点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！