Bar*_*iej 5 algorithm tree graph
我们得到一个带N (up to 100,000)节点的树.每个边缘被加权任一+1或-1和节点从编号1到N.(A, B)存在多少无序对,使得在路径上A -> X -> B,其中X(X != A && X != B)是路径之间的某些顶点A和B,路径上的边权重之和A -> X是,0并且路径上边缘权重的总和X -> B是0？
因此,我们只关心偶数路径长度,否则边缘权重的总和不能0.我们不能重复对潜在A和B,否则我们得到一个O(N^2)解决方案,这将不低于1秒运行.有关如何解决的任何提示？该程序应该在1秒内运行,因此一个O(N)或一个O(N logN)解决方案可以工作.
编辑:但是,如果我们可以计算从每个节点开始的良好路径的数量,我们就能够解决问题.有可能计算出来吗？听起来对我而言,但我不确定.
G. *_*ach -1
我不知道这是否有用，但如果有的话，我认为您可以使用此属性：\n取一对(A,B)存在此类路径的路径。然后我们知道路径的边权重之和（我将其称为末端顶点的距离）A -> ... -> B := d(A,B) = 0，因为
d(A,B) = d(A,X) + d(X,B) = 0 + 0 = 0
正如您所说，我们只关心长度相等的路径；这表明，在实际检查对时，我们首先用两种颜色给树着色（因为所有树都是二分树），这可以在 \xce\x98(n) 中贪婪地完成，并且只考虑每个颜色组内的顶点对。当然，这并不会提高我们必须考虑的对数的复杂性，因为每种颜色仍然有 (n/2)*(n-1)/2 个顶点，并且该项位于 \xce\x98 中(n^2) 其中n是顶点数。
现在，正如您所说，您可以使用 BFS 计算 \xce\x98(n^2) 中的路径并检查每个颜色组中的所有顶点对。这是另一个可能对您有帮助的想法：
\n\n假设我们有两个顶点 V 和 Ud(A,V) = d(A,U)。我们有两种情况：
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。
两条路在某处分叉；令路径分叉的顶点为 K。然后我们有
\n\nd(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距离；或者，简化为，仅在任一顶点到 的距离上。更一般地说，这一事实仅意味着任一顶点位于从到另一个顶点的路径上的情况，因此如果后一种情况不是这种情况，则无法通过相等距离真正判断任何内容。AKKd(A,U) = d(A,V)d(U,V) = 0A
我不知道这些是否会对您有所帮助。我无法弄清楚如何在次二次时间内实现您所要求的目标，并且我认为这是不可能的；对我来说，这个问题感觉与所有对最短路径有很大关系，其时间复杂度为 O(n^2)，对每个顶点使用 BFS 作为起始顶点。不过，这更像是一种模糊的感觉，而不是任何隐约类似于令人信服的论点的东西。
\n