algorithm - 位于给定树的多个顶点之间的边

Question

我有一棵树，有 N 个顶点 v1, v2, v3.... vN 。树挂在顶点 v1 上。现在我在树中选择了一些随机路径。如何知道树中是否有一条边位于所有这些选定的路径上？

编辑-所有路径都是双向的。

Answer 1

正如 G. Bach 所建议的，您遍历每条路径，并在此过程中为每条边记录它包含在路径中的次数。最后，您可以迭代边缘集，并且与路径数具有相同计数的边缘（或边缘）将是位于所有选定路径上的边缘。

由于一棵树中确实有n-1边，所以这个算法是O(n)，我猜它已经是最有效的了。