5

我们得到一棵带有N (up to 100,000)节点的树。每条边的权重都是+1or -1，节点的编号从1到N。(A, B)在路径上存在多少个无序对A -> X -> B，其中X( ) 是和X != A && X != B之间路径上的某个顶点，路径上的边权重之和为 ，路径上的边权重之和为？ABA -> X0X -> B0

因此，我们只关心偶数路径长度，否则边缘权重的总和不能是0。我们不能迭代潜在的Aand B，否则我们会得到一个O(N^2)不会在 1 秒内运行的解决方案。关于如何解决它的任何提示？该程序应在 1 秒内运行，因此O(N)orO(N logN)解决方案将起作用。

编辑：但是，如果我们可以计算从每个节点开始的好路径的数量，我们将能够解决这个问题。可以计算这个吗？对我来说听起来很DP，但我不确定。

4

2 回答 2

0

我将在下面开发一个算法，从O(N^2). 通过一个小的观察，我们可以将复杂性更改为更小的东西。我不太确定它会是什么（O(N)或O(NlnN)），但它似乎小于O(N^2).

  1. 在树中，选择任意叶节点x0，并创建一个空列表L0。
  2. 跟随叶子节点向上一个分支。如果列表非空，则将此边缘权重的值添加到列表的每个项中，这将记录到目前为止的边缘权重的累积和。
  3. 将此边缘权重附加到列表中。
  4. 如果这个新节点只有 2 个分支，则通过沿唯一的新方向上行并更新来转到第 2 步L0。重复，直到新节点上有 3 个或更多分支。
  5. 对于每个分支（除了我们来自的方向）递归地从步骤 1 开始在每个子树上，除了在该子树中将此节点标记为特殊节点。当递归回到这个节点时，它将合并（步骤 5）并停止。
  6. 合并：我们现在有一组列表L0, L1, L2, ...必须合并到L0. 这些列表中的每一个都代表不同的路径及其各自的累积总和。对于每个列表中的每一对，将m这些和等于零的次数添加到计数器。这为图中的每个可能路径关联了一个总和。创建一个新列表L0，它是 set 的串联L0, L1, L2, ...。

上面的算法有效，但由于我们对每个图路径执行求和，因此成本必须至少为O(N^2).

这里的诀窍是不计算每条路径。相反，如果我们对列表进行排序，确定两个排序大小的列表k1,k2是否具有固定总和c可以通过简单地遍历列表来完成，一个向前一个向后。因此，可以对操作中的每对列表进行计数，而k1+k2不是k1*k2像以前那样进行操作。合并列表也很简单，并且具有相同的复杂性，因为它们已经排序。

奖励：上述方法可以简单地扩展到任意边缘权重（不仅仅是-1, 1）和任意固定总和（不仅仅是零）。

于 2013-04-08T04:40:50.337 回答
-1

我不知道这是否有用，但如果有的话，我认为你可以使用这个属性：取一对(A,B)存在这样的路径。然后我们知道路径的边权重之和（我将其称为末端顶点的距离）A -> ... -> B := d(A,B) = 0，因为

d(A,B) = d(A,X) + d(X,B) = 0 + 0 = 0

正如您所说，我们只关心偶数长度的路径；这表明在实际检查对时，我们首先用两种颜色为树着色（因为所有树都是二分的），这可以在 Θ(n) 中贪婪地完成，并且只考虑每个颜色组内的顶点对。当然，这并没有提高我们必须考虑的对数的复杂性，因为我们在每种颜色中仍然有 (n/2)*(n-1)/2 个顶点，并且该术语在 Θ(n^ 2) 其中n是顶点数。

现在正如您所说，您可以使用 BFS 计算 Θ(n^2) 中的路径并检查每个颜色组中的所有顶点对。这是另一个可能对您有所帮助的想法：

假设我们有两个顶点 V 和 U d(A,V) = d(A,U)。我们有两种情况：

  1. A -> ... -> V = A -> ... -> U -> ... -> V, 表示 U (WLOG) 位于从 A 到 V 的唯一路径上。那么我们有

    d(A,V) = d(A,U) + d(U,V) <=> d(A,V) = d(A,V) + d(U,V) <=> d(U,V) = 0

    因此，如果 U 和 V 位于同一条路径上并且到 A 的距离相等，则距离d(U,V) = 0。

  2. 两条路在某处分叉；让路径分叉的顶点为K。然后我们有

    d(A,V) = d(A,K) + d(K,V) <=> d(K,V) = d(A,V) - d(A,K)和

    d(A,U) = d(A,K) + d(K,U) <=> d(K,U) = d(A,U) - d(A,K)和

    d(U,V) = d(K,U) + d(K,V) = d(A,U) + d(A,V) - 2*d(A,K) = 2*(d(A,U) - d(A,K)) = 2 * d(K,U)

    因此，如果U并且V不在同一条路径上，它们之间的距离取决于顶点必须到A的距离和距离A必须到的距离K；或者，简化，就在任一顶点到 的距离上K。更一般地说，这一事实d(A,U) = d(A,V)仅意味着d(U,V) = 0任何一个顶点位于从A另一个顶点的路径上，所以如果后一种情况不是这种情况，你就不能真正以相等的距离告诉任何东西。

这是否会帮助你，我不知道。我无法弄清楚如何在次平方时间内实现您的要求，我认为这是不可能的；对我来说，这个问题感觉与所有对最短路径有很大关系，它的时间复杂度为 O(n^2)，每个顶点使用 BFS 作为起始顶点。不过，这更像是一种模糊的感觉，甚至比任何看似令人信服的论点都模糊。

于 2013-04-06T03:35:49.310 回答