lca

Documentation

Index

• type RootedTree
  • func NewLCA(size, root int) RootedTree
  • func (t *RootedTree) AddEdge(v, w int)
  • func (t *RootedTree) Init()
  • func (t *RootedTree) Lca(v, w int) int
• type Tree

Types

type RootedTree

type RootedTree struct {
	Tree
	Root   int
	Depth  []int
	Parent [][]int //Parent[v][k] = 2^k th parent of v
	// contains filtered or unexported fields
}

func NewLCA

func NewLCA(size, root int) RootedTree

NewLCA returns rooted tree of size n.

func (*RootedTree) AddEdge

func (t *RootedTree) AddEdge(v, w int)

AddEdge adds new edge connecting the v-th and the w-th node to the rooted tree instance.

func (*RootedTree) Init

func (t *RootedTree) Init()

Init prepares for incoming Lca() queries.

func (*RootedTree) Lca

func (t *RootedTree) Lca(v, w int) int

Lca returns the lowest common ancestor of the v-th and w-th node.

type Tree

type Tree struct {
	Size int
	Adj  [][]int
}