我有一个加权树形图，其中所有权重都是正数。我需要一个算法来解决以下问题。树形图 - 找到有多少对顶点，它们之间的路径上的边的总和是C

该图中有多少对顶点，为此它们之间的边的权重之和等于C？

我想到了一个解决方案，多数民众赞成O(n^2)

对于每一个我们从它开始DFS当该合计变得比C更大停止它的顶点。由于边数为n-1，这明显给我们提供了一个解决方案。

但我们能做得更好吗？

来源

2014-03-24 Arek Krawczyk

该图是否定向？ – amit

是的，有一个O（n polylog n + k）分而治之算法来寻找k对。 –

标题显示“find”，但问题主体询问“多少” - 这是什么？你想找到他们所有的人，或只是他们的计数？ – Dukeling