给定一棵树，在Log（n）中找到从节点'a'到节点'b'的路径中的第k个节点？

Question

给定一棵树，我需要找到从'a'到'b'的路径中'第k个节点。这意味着我需要在从节点'a'到节点'b'的路径中的'第k'位置找到节点。我正在思考最低共同祖先和/或重光分解的问题，但我不确定这是否是这样做的。任何正确的方向指导表示赞赏。

详情：

• 的树不是二叉树。它是一个具有n-1个边，n个顶点和无周期的无向图。只是你的常规树
• 树的顶点编号从1到n。有n-1个无向边连接这些顶点的n-1对
• 'a'和'b'是树中从1到n编号的任何2个顶点。我们要在从'a'到'b'的路径中找到'第k个节点。这是保证数“k”的值是< =从路径中的节点的数目“A”到“b”

甲BFS施加在每个查询（第k个节点从“A”到“b” ）不是一个选项，因为查询的数量很大。

Answer 1

做最低的共同祖先，并保持每个节点的深度（距根的距离）。

接下来找出第k个节点是否位于a到lca或lca到b的一部分。深度差异是它们之间的节点数量，所以如果depth[a] - depth[lca] > k那么该节点位于lca-b部分。

如果节点位于a到lca部分，只需找到第k个祖先。应该使用您预先计算的LCA数据记录（N）。

如果节点位于b到lca部分，则可以计算k'，这是距第b个节点（k' = 1 + depth[a] + depth[b] - 2*depth[lca] - k)）第k个节点的距离，然后获得b的k'祖先（使用LCA数据也很容易）。

总体而言，所有查找都是logN，其他步骤都是常量，因此您需要为每个查询执行O（LogN）。