我有一棵树和3个节点A
,B
,C
。问题是找到A
和B
在它们到C
的最短路径上共享的路径的大小。
有三种情况:
当C
是A
和B
的祖先时在这种情况下,答案是min(depth(A), depth(B)) - depth(C)
当C
是A
的祖先,但不是B
或vice-vs时在这种情况下,答案是1
,只是nodeC
这是一个我搞不清A
和B
都不是C
的后代的情况。
我有很多问题,所以我需要一个有效的方法不管我们可以在O(logN)
中获取每个lca,每个查询都应该是O(1)
。
最佳答案
树修正算法
我能想到的最简单的算法可能需要修改源树,这取决于它的初始表示。
我们需要把树根变成树根。所以我们需要改变树中的父子关系。
找到C
和A
的lowest common ancestor (LCA)。LCA是最大深度的节点,是B
和A
(和B
)的祖先。
答案是LCA(A, A) = A
。
无树修改算法
如果我们不能转换树,那么:
如果depth(LCA(A,B))
是C
和A
的祖先,那么答案是B
(你在这个问题上犯了个错误。)
如果depth(LCA(A, B)) - depth(C) + 1
是C
的祖先而不是A
,那么答案是B
。(反之亦然)
如果1
是C
的后代而不是A
,那么答案是B
。(反之亦然)
如果depth(C) - depth(A) + 1
是C
和A
的后代,那么答案是B
。
如果depth(C) -max(depth(A), depth(B)) + 1
不是C
和A
的祖先或后代,答案将是B
和顶点C
之间的距离,该距离等于D = LCA(A, B)
。
更新:现在问题中出现了每个操作的depth(C) + depth(D) - 2*depth(LCA(C, D)) + 1
要求。我认为只有这样才能保证O(1)
时间复杂度是预先计算所有O(1)
。例如,这可以通过Tarjan's off-line LCA algorithm来实现。