给定一棵树，在 Log(n) 中找到从节点 'a' 到节点 'b' 的路径中的第 k 个节点？
Given a tree, find the kth node in the path from node 'a' to node 'b' in Log(n)?
给定一棵树，我需要找到从 'a' 到 'b' 路径中的第 'k' 个节点。这意味着我需要在从节点'a'到节点'b'的路径中找到'kth'位置的节点。我在考虑 Lowest-common-ancestor and/or heavy-light decomposition 的路线，但我不确定这是否是这样做的方法。感谢任何正确方向的指导。
详情：
- 树不是二叉树。它是一个无向图，有 n-1 条边、n 个顶点且没有环。只是你的普通树
- 这棵树的顶点编号从 1 到 n。有n-1条无向边连接n-1对这些顶点
- 'a' 和 'b' 是树中编号从 1 到 n 的任意 2 个顶点。我们要在从'a'到'b'的路径中找到第'k'个节点。保证'k'的值<=从'a'到'b'
路径中的节点数
应用于每个查询（从 'a' 到 'b' 的第 k 个节点）的 BFS 不是一个选项，因为查询的数量很大。
执行 lowest-common-ancestor，并为每个节点保留其深度（到根的距离）。
接下来判断第k个节点是在a到lca还是lca到b部分。深度的差异是它们之间的节点数，因此如果 depth[a] - depth[lca] > k 则节点在 lca-b 部分。
如果节点在a到lca部分，只需要找到a的第k个祖先。使用您预先计算的 LCA 数据应该是 log(N)。
如果节点在 b 到 lca 部分，那么你可以计算 k'，它是第 k 个节点到 b 的距离 (k' = 1 + depth[a] + depth[b] - 2*depth[lca] - k))，然后得到 b 的 k' 祖先（再次简单与 LCA 数据）。
总的来说，所有查找都是 logN，其他步骤是不变的，因此每个查询执行 O(LogN)。
给定一棵树，我需要找到从 'a' 到 'b' 路径中的第 'k' 个节点。这意味着我需要在从节点'a'到节点'b'的路径中找到'kth'位置的节点。我在考虑 Lowest-common-ancestor and/or heavy-light decomposition 的路线，但我不确定这是否是这样做的方法。感谢任何正确方向的指导。
详情：
- 树不是二叉树。它是一个无向图，有 n-1 条边、n 个顶点且没有环。只是你的普通树
- 这棵树的顶点编号从 1 到 n。有n-1条无向边连接n-1对这些顶点
- 'a' 和 'b' 是树中编号从 1 到 n 的任意 2 个顶点。我们要在从'a'到'b'的路径中找到第'k'个节点。保证'k'的值<=从'a'到'b' 路径中的节点数
应用于每个查询（从 'a' 到 'b' 的第 k 个节点）的 BFS 不是一个选项，因为查询的数量很大。
执行 lowest-common-ancestor，并为每个节点保留其深度（到根的距离）。
接下来判断第k个节点是在a到lca还是lca到b部分。深度的差异是它们之间的节点数，因此如果 depth[a] - depth[lca] > k 则节点在 lca-b 部分。
如果节点在a到lca部分，只需要找到a的第k个祖先。使用您预先计算的 LCA 数据应该是 log(N)。
如果节点在 b 到 lca 部分，那么你可以计算 k'，它是第 k 个节点到 b 的距离 (k' = 1 + depth[a] + depth[b] - 2*depth[lca] - k))，然后得到 b 的 k' 祖先（再次简单与 LCA 数据）。
总的来说，所有查找都是 logN，其他步骤是不变的，因此每个查询执行 O(LogN)。