c++ - 树上的路径查询

Question

给定一棵树和Q要回答的查询。在每个查询中，您将获得 2 个节点u & v。您应该返回路径，例如u -> v1 -> v2... -> v

我有一种天真的方法来为每个查询执行 DFS，但它可以做得更好吗？是否可以进行任何类型的预处理？（我是图表新手！如果我在某处出错，请帮助我并纠正我）

标签： c++algorithmgraphgraph-theorygraph-algorithm

Answer 1

我假设在每个树节点上你也有父节点，你也可以使用它在树中上升。

有了这个假设，这个问题似乎就是寻找最低共同祖先的问题。这是一个标准问题，您可以在网上轻松找到如何解决它。

一旦你拥有最低的共同祖先，你的路径将从 u--><lowest_common_ancestor>-->v

只要找到最低的共同祖先，那么进一步的算法对你来说就会变得显而易见。