树中的共享路径

Question

我有一棵树和3个节点A,B,C。问题是找到A和[=11的路径的大小=] 将分享他们到 C.

的最短路径

有3个案例：

1. 当 C 是 A 和 B 的祖先时。在这种情况下，答案是 min(depth(A), depth(B)) - depth(C)

2. 当 C 是 A 而不是 B 的祖先时，反之亦然。在这种情况下，答案是1，只是节点C

3. 这是我无法弄清楚的情况，因为 A 和 B 都不是 C 的后代。

我会有很多疑问，所以我需要一种有效的方法。忽略我们可以在 O(logN) 中获取每个 LCA，每个查询应该是 O(1).

Answer 1

修改树的算法

我能想到的最简单的算法可能需要根据其初始表示修改源代码树。

1. 我们需要使 C 成为树的根。所以我们需要改变树内的父子关系。

2. 找到A和B的lowest common ancestor (LCA)。 LCA 是具有最大深度的节点，它是 A 和 B（以及 LCA(A, A) = A）的祖先。

3. 答案是depth(LCA(A,B))。

没有修改树的算法

如果我们不能转换树那么：

1. 如果 C 是 A 和 B 的祖先，那么答案是 depth(LCA(A, B)) - depth(C) + 1。 （你的问题有误。）
   

2. 如果 C 是 A 而不是 B 的祖先，那么答案是 1。 （反之亦然）

3. 如果 C 是 A 而不是 B 的后代，那么答案是 depth(C) - depth(A) + 1。 （反之亦然）
   

4. 如果 C 是 A 和 B 的后代，那么答案是 depth(C) - max(depth(A), depth(B)) + 1.
   

5. 如果 C 不是 A 和 B 的祖先或后代，则答案是 C 和顶点 D = LCA(A, B) 之间的距离相等至 depth(C) + depth(D) - 2*depth(LCA(C, D)) + 1.
   

---

更新：现在问题中出现了每个操作要求O(1)。我认为要保证 O(1) 时间复杂度，您唯一可以做的就是预先计算所有 LCA(i, j)。例如，可以使用 Tarjan's off-line LCA algorithm.

来完成

Answer 2

如上述回答中的，一种方法可以根据他所说的方式，即通过将树的根设为C，然后检查路径。

另一种方法是以类似的方式找到 A 和 B 的最低共同后裔 (LCD)。简而言之，我们可以找到第一个节点A 和 B 的路径在走向 C 时会相交 ，然后给出从该节点到 C 的路径的大小。然后可能有几种情况：

1. A 和 B（朝向 C）的 LCD 是 A：return从 A 到 C 的路径长度
2. A 和 B（朝向 C）的 LCD 是 B：return 从 B 到 C 的路径长度
3. A和B的LCD（向C方向）是C：return 0
4. A和B的LCD（朝向C）是一个节点D：return从D到C的路径长度