Function LowestCommonAncestor

graph/lowestcommonancestor.go:113–123

For each node, we will precompute its ancestor above him, its ancestor two nodes above, its ancestor four nodes above, etc. Let's call `jump[j][u]` is the `2^j`-th ancestor above the node `u` with `u` in range `[0, numbersVertex)`, `j` in range `[0,MAXLOG)`. These information allow us to jump from a

(tree *Tree)

// Let's call `jump[j][u]` is the `2^j`-th ancestor above the node `u` with `u` in range `[0, numbersVertex)`, `j` in range `[0,MAXLOG)`.
// These information allow us to jump from any node to any ancestor above it in `O(MAXLOG)` time.
func LowestCommonAncestor(tree *Tree) {
	// call dfs to compute depth from the root to each node and the parent of each node.
	tree.dfs(tree.root, tree.root)

	// compute jump[j][u]
	for j := 1; j < tree.MAXLOG; j++ {
		for u := 0; u < tree.numbersVertex; u++ {
			tree.jump[j][u] = tree.jump[j-1][tree.jump[j-1][u]]
		}
	}
}