Posts Least Common Ancestor (LCA)
Post
Cancel

Least Common Ancestor (LCA)

Jackson Goerner Apr 20, 2021 2021-04-20T22:00:00+10:00
Dec 13, 2021 2021-12-13T11:01:10+11:00 22 min

Where is this useful?

The Least Common Ancestor (LCA) data structure is useful wherever you have a directed graph where every vertex has out-degree \(\leq 1\). In more common terms, each vertex has a unique determined ‘parent’, or it is a root node, with no parent. The most common (and almost always only) example being a rooted tree.

On these particular graphs, the LCA gives us a fast way to move ‘up’ the graph (Towards your parents). In particular, we can use this to find the least common ancestor in \(\log (N)\) time, where the data structure gets its name from.

Reusing the analogy of parenting vertices, a vertex \(u\) is an ancestor of \(v\) if \(u\) is \(v\)’s parent, or \(v\)’s parent’s parent, and so on. As long as there is a line of ‘parentage’ connecting \(v\) to \(u\), \(u\) is an ancestor of \(v\). We consider \(v\) to also be it’s own ancestor.

The least common ancestor problem then requires, given two vertices \(x\) and \(y\), to find a vertex \(z\) in the graph such that \(z\) is an ancestor of both \(x\) and \(y\), but there is no vertex \(z’ \neq z\) such that \(z\) is an ancestor of \(z’\) and \(z’\) is an ancestor of \(x\) and \(y\) (In the tree example, we just want to find the lowest depth vertex whose subtree contains boths \(x\) and \(y\)).

Note that the least common ancestor can be \(x\) or \(y\), if \(x\) is an ancestor of \(y\) or vice-versa.

Implementing the Data Structure

Interface

Let’s start by defining an interface for this data structure, and then slowly implement our methods.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class LCA:
"""
vertices are represented as numbers 0->n-1.
"""

    def __init__(self, n_vertices):
        self.n = n_vertices
        self.adjacent = [[] for _ in range(self.n)]

    def add_edge(self, u, v, weight=1):
        self.adjacent[u].append((v, weight))
        self.adjacent[v].append((u, weight))

    def build(self, root):
        # Once edges are added, build the tree/data structure.
        pass # TODO

    def query(self, u, v, root=None):
        # What is the lowest common ancestor of u, v?
        # Extension: Make this query from any root vertex you want.
        pass # TODO

    def dist(self, u, v):
        # Find the distance between two vertices - very simple if we have LCA.
        pass # TODO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

template<typename T = int> struct LCA {
    // vertices are represented as numbers 0->n-1.
    int n; vector<vector<pair<int, T> > > adjacent;

    LCA(int n_vertices) : n(n_vertices), adjacent(n) { }

    void add_edge(int u, int v, T weight=1) {
        adjacent[u].emplace_back(v, weight);
        adjacent[v].emplace_back(u, weight);
    }

    void build(int root=0) {
        // Once edges are added, build the tree/data structure.
        // TODO
    }

    int query(int u, int v, int root=-1) {
        // What is the lowest common ancestor of u, v?
        // Extension: Make this query from any root vertex you want.
        // TODO
    }

    T dist(int u, int v) {
        // Find the distance between two vertices - very simple if we have LCA.
        // TODO
    }
}

Useful data

First off, let’s save some intermediary data that will make our life a lot easier, and strictly define the tree structure. We’ll introduce three arrays: parent, level and length.

  • parent stores the direct parent of any vertex in the rooted tree.
  • level stores the level of the tree the vertex is at (Number of edges from it to the root)
  • length stores the length of the vertex to the root (Using edge weights).

We’ll populate these fields in the build method, since all edges should be added by then.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class LCA:
"""
vertices are represented as numbers 0->n-1.
"""

    def __init__(self, n_vertices):
        self.n = n_vertices
        self.adjacent = [[] for _ in range(self.n)]

    def add_edge(self, u, v, weight=1):
        self.adjacent[u].append((v, weight))
        self.adjacent[v].append((u, weight))

    def dfs(self, source, c_parent, c_level, c_length):n
        # Search from the source down the tree and set parent, level, length accordingly.n
        self.parent[source] = c_parentn
        self.level[source] = c_leveln
        self.length[source] = c_lengthn
        for child, weight in self.adjacent[source]:n
            if child != c_parent:n
                self.dfs(child, source, c_level + 1, c_length + weight)n

    def build(self, root):
        # Once edges are added, build the tree/data structure.
        self.parent = [None]*self.nn
        self.level = [None]*self.nn
        self.length = [None]*self.nn
        self.dfs(root, -1, 0, 0)n

    def query(self, u, v, root=None):
        # What is the lowest common ancestor of u, v?
        # Extension: Make this query from any root vertex you want.
        pass # TODO

    def dist(self, u, v):
        # Find the distance between two vertices - very simple if we have LCA.
        pass # TODO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

template<typename T = int> struct LCA {
    // vertices are represented as numbers 0->n-1.
    int n; vector<vector<pair<int, T> > > adjacent;
    vi parent, level;n
    vector<T> length;n

    LCA(int n_vertices) : n(n_vertices), adjacent(n), parent(n), level(n), length(n) { }m

    void add_edge(int u, int v, T weight=1) {
        adjacent[u].emplace_back(v, weight);
        adjacent[v].emplace_back(u, weight);
    }

    void dfs(int source, int c_parent, int c_level, T c_length) {n
        // Search from the source down the tree and set parent, level, length accordingly.n
        parent[source] = c_parent;n
        level[source] = c_level;n
        length[source] = c_length;n
        for (auto v: adjacent[source])n
            if (v.first != c_parent)n
                dfs(v.first, source, c_level+1, c_length+v.second);n
    }

    void build(int root=0) {
        // Once edges are added, build the tree/data structure.
        dfs(root, -1, 0, 0);n
    }

    int query(int u, int v, int root=-1) {
        // What is the lowest common ancestor of u, v?
        // Extension: Make this query from any root vertex you want.
        // TODO
    }

    T dist(int u, int v) {
        // Find the distance between two vertices - very simple if we have LCA.
        // TODO
    }
}

So now we can query many useful characteristics of vertices in rooted trees. Now for the interesting part: let’s start creating data unique to the LCA structure.

Ancestor Array

LCA gets its fast queries by precomputing a special array, called ancestor. Ancestor is a 2 dimensional array with ancestor[v][k] storing the ancestor of vertex v \(2^k\) edges towards the root. As an example, ancestor[v][0] is parent[v] (Parent is just ancestor 1 edge towards the root), and ancestor[v][1] is parent[parent[v]] where appropriate (2 edges towards root is same as parent’s parent).

If you just populated this array by searching up the tree \(2^k\) steps each time, you’d have worst case complexity \(O(n^2)\) to build the array. Luckily, we can use the fact that ancestor[v][k] = ancestor[ancestor[v][k-1]][k-1] (In other words, you can move \(2^k\) steps towards the root by first moving \(2^{k-1}\) steps, which we’ve already computed, and then another \(2^{k-1}\) steps from this new position). This reduces the complexity to \(O(n\log_2(n))\)

We do this so that we can find the ancestor \(m\) edges towards the root for any arbitrary \(m\) in \(\log_2(m)\) time, while only using \(\log_2(n)\) space. We’ll see how this gets done later.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class LCA:
"""
vertices are represented as numbers 0->n-1.
"""

    # number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6.n
    MAX_LOG = 20n

    def __init__(self, n_vertices):
        self.n = n_vertices
        self.adjacent = [[] for _ in range(self.n)]

    def add_edge(self, u, v, weight=1):
        self.adjacent[u].append((v, weight))
        self.adjacent[v].append((u, weight))

    def dfs(self, source, c_parent, c_level, c_length):
        # Search from the source down the tree and set parent, level, length accordingly.
        self.parent[source] = c_parent
        self.level[source] = c_level
        self.length[source] = c_length
        for child, weight in self.adjacent[source]:
            if child != c_parent:
                self.dfs(child, source, c_level + 1, c_length + weight)

    def build(self, root):
        # Once edges are added, build the tree/data structure.
        self.parent = [None]*self.n
        self.level = [None]*self.n
        self.length = [None]*self.n
        self.dfs(root, -1, 0, 0)
        # Compute ancestorn
        self.ancestor = [[-1]*self.MAX_LOG for _ in range(self.n)]n
        # Initial step: ancestor[v][0] = parent[v]n
        for v in range(self.n):n
            self.ancestor[v][0] = self.parent[v]n
        # Now, compute ancestor[v][k] from 1->MAX_LOGn
        for k in range(1, self.MAX_LOG):n
            for v in range(self.n):n
                if self.ancestor[v][k-1] != -1:n
                    # Move 2^{k-1} up, then 2^{k-1} again.n
                    self.ancestor[v][k] = self.ancestor[self.ancestor[v][k-1]][k-1]n

    def query(self, u, v, root=None):
        # What is the lowest common ancestor of u, v?
        # Extension: Make this query from any root vertex you want.
        pass # TODO

    def dist(self, u, v):
        # Find the distance between two vertices - very simple if we have LCA.
        pass # TODO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

template<typename T = int> struct LCA {
    // vertices are represented as numbers 0->n-1.
    // number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6.n
    int MAX_LOG = 20;n
    int n; vector<vector<pair<int, T> > > adjacent;
    vi parent, level;
    vvi ancestor;n
    vector<T> length;

    LCA(int n_vertices) : n(n_vertices), adjacent(n), parent(n), level(n), length(n) { }

    void add_edge(int u, int v, T weight=1) {
        adjacent[u].emplace_back(v, weight);
        adjacent[v].emplace_back(u, weight);
    }

    void dfs(int source, int c_parent, int c_level, T c_length) {
        // Search from the source down the tree and set parent, level, length accordingly.
        parent[source] = c_parent;
        level[source] = c_level;
        length[source] = c_length;
        for (auto v: adjacent[source])
            if (v.first != c_parent)
                dfs(v.first, source, c_level+1, c_length+v.second);
    }

    void build(int root=0) {
        // Once edges are added, build the tree/data structure.
        dfs(root, -1, 0, 0);
        // Compute ancestorn
        ancestor.assign(n, vi(MAX_LOG, -1));n
        // Initial step: ancestor[v][0] = parent[v]n
        for (int v=0; v<n; v++)n
            ancestor[v][0] = parent[v];n
        // Now, compute ancestor[v][k] from 1->MAX_LOGn
        for (int k=1; k < MAX_LOG; k++)n
            for (int v=0; v<n; v++)n
                if (ancestor[v][k-1] != -1) {n
                    // Move 2^{k-1} up, then 2^{k-1} again.n
                    ancestor[v][k] = ancestor[ancestor[v][k-1]][k-1];n
                }n
    }

    int query(int u, int v, int root=-1) {
        // What is the lowest common ancestor of u, v?
        // Extension: Make this query from any root vertex you want.
        // TODO
    }

    T dist(int u, int v) {
        // Find the distance between two vertices - very simple if we have LCA.
        // TODO
    }
}

Query

That’s actually most of the ingenuity out of the way, now we can get to implementing query.

Provided we want the LCA with respect to the root we called build from, we can define the LCA l of u and v in the following way:

l is the ancestor of u and v maximising level[l].

We also know that level[l] <= min(level[u], level[v]). Using this, we can calculate query(u, v) by:

  • Finding the ancestors of u and v (call them a1, a2) such that level[a1] = level[a2] = min(level[u], level[v]).
  • Keep moving a1 and a2 towards the root (higher and higher ancestors) until a1 == a2. Then a1 and a2 are the LCA of u and v.

We can do both of these things on \(\log_2(n)\) time with this ancestor array we’ve generated. Let’s see how:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

class LCA:
"""
vertices are represented as numbers 0->n-1.
"""

    # number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6.
    MAX_LOG = 20

    def __init__(self, n_vertices):
        self.n = n_vertices
        self.adjacent = [[] for _ in range(self.n)]

    def add_edge(self, u, v, weight=1):
        self.adjacent[u].append((v, weight))
        self.adjacent[v].append((u, weight))

    def dfs(self, source, c_parent, c_level, c_length):
        # Search from the source down the tree and set parent, level, length accordingly.
        self.parent[source] = c_parent
        self.level[source] = c_level
        self.length[source] = c_length
        for child, weight in self.adjacent[source]:
            if child != c_parent:
                self.dfs(child, source, c_level + 1, c_length + weight)

    def build(self, root):
        # Once edges are added, build the tree/data structure.
        self.parent = [None]*self.n
        self.level = [None]*self.n
        self.length = [None]*self.n
        self.dfs(root, -1, 0, 0)
        self.ancestor = [[-1]*self.MAX_LOG for _ in range(self.n)]
        # Initial step: ancestor[v][0] = parent[v]
        for v in range(self.n):
            self.ancestor[v][0] = self.parent[v]
        # Now, compute ancestor[v][k] from 1->MAX_LOG
        for k in range(1, self.MAX_LOG):
            for v in range(self.n):
                if self.ancestor[v][k-1] != -1:
                    # Move 2^{k-1} up, then 2^{k-1} again.
                    self.ancestor[v][k] = self.ancestor[self.ancestor[v][k-1]][k-1]

    def query(self, u, v, root=None):
        # What is the lowest common ancestor of u, v?
        # Extension: Make this query from any root vertex you want.

        if root is not None:n
            pass # TODOn
        # assume that u is higher up than v, to simplify the code belown
        if self.level[u] > self.level[v]:n
            u, v = v, un
        # STEP 1: set u and v to be ancestors with the same leveln
        for k in range(self.MAX_LOG-1, -1, -1):n
            if (self.level[v] - (1 << k) >= self.level[u]):n
                # If v is 2^k levels below u, move it up 2^k levels.n
                v = self.ancestor[v][k]n
        # We can be certain that level[u] = level[v]. Reason: binary representation of all natural numbers.n
        # Do we need to move to step 2?n
        if (u == v): return un
        # STEP 2: find the highest ancestor where u != v. Then the parent is the LCAn
        for k in range(self.MAX_LOG-1, -1, -1):n
            if (self.ancestor[u][k] != self.ancestor[v][k]):n
                # Move up 2^k stepsn
                u = self.ancestor[u][k]n
                v = self.ancestor[v][k]n
        return self.parent[u]n

    def dist(self, u, v):
        # Find the distance between two vertices - very simple if we have LCA.
        pass # TODO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

template<typename T = int> struct LCA {
    // vertices are represented as numbers 0->n-1.
    // number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6.
    int MAX_LOG = 20;
    int n; vector<vector<pair<int, T> > > adjacent;
    vi parent, level;
    vvi ancestor;
    vector<T> length;

    LCA(int n_vertices) : n(n_vertices), adjacent(n), parent(n), level(n), length(n) { }

    void add_edge(int u, int v, T weight=1) {
        adjacent[u].emplace_back(v, weight);
        adjacent[v].emplace_back(u, weight);
    }

    void dfs(int source, int c_parent, int c_level, T c_length) {
        // Search from the source down the tree and set parent, level, length accordingly.
        parent[source] = c_parent;
        level[source] = c_level;
        length[source] = c_length;
        for (auto v: adjacent[source])
            if (v.first != c_parent)
                dfs(v.first, source, c_level+1, c_length+v.second);
    }

    void build(int root=0) {
        // Once edges are added, build the tree/data structure.
        dfs(root, -1, 0, 0);
        // Compute ancestor
        ancestor.assign(n, vi(MAX_LOG, -1));
        // Initial step: ancestor[v][0] = parent[v]
        for (int v=0; v<n; v++)
            ancestor[v][0] = parent[v];
        // Now, compute ancestor[v][k] from 1->MAX_LOG
        for (int k=1; k < MAX_LOG; k++)
            for (int v=0; v<n; v++)
                if (ancestor[v][k-1] != -1) {
                    // Move 2^{k-1} up, then 2^{k-1} again.
                    ancestor[v][k] = ancestor[ancestor[v][k-1]][k-1];
                }
    }

    int query(int u, int v, int root=-1) {
        // What is the lowest common ancestor of u, v?
        // Extension: Make this query from any root vertex you want.
        if (root != -1) {n
            // TODOn
        }n
        // assume that u is higher up than v, to simplify the code belown
        if (level[u] > level[v]) swap(u, v);n
        // STEP 1: set u and v to be ancestors with the same leveln
        for (int k=MAX_LOG-1, k>=0; k--)n
            if (level[v] - (1 << k) >= level[u]) {n
                // If v is 2^k levels below u, move it up 2^k levels.n
                v = ancestor[v][k];n
            }n
        // We can be certain that level[u] = level[v]. Reason: binary representation of all natural numbers.n
        // Do we need to move to step 2?n
        if (u == v) return un
        // STEP 2: find the highest ancestor where u != v. Then the parent is the LCAn
        for (int k=MAX_LOG; k>=0; k--)n
            if (ancestor[u][k] != ancestor[v][k]) {n
                // Move up 2^k stepsn
                u = ancestor[u][k];n
                v = ancestor[v][k];n
            }n
        return parent[u];n
    }

    T dist(int u, int v) {
        // Find the distance between two vertices - very simple if we have LCA.
        // TODO
    }
}

Nice! That’s the main functionality of LCA completed.

Corrolaries

Let’s quickly tackle the two remaining implementations:

  • Calculating the distance between two vertices u and v is the same as calculating the distance between u and query(u, v), and adding that to the distance between v and query(u, v)
  • Calculating the LCA from a particular root, just requires a slight change in perspective. For two vertices u and v, and custom root r, the LCA will always be one of query(u, v), query(u, r) or query(v, r).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

class LCA:
"""
vertices are represented as numbers 0->n-1.
"""

    # number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6.
    MAX_LOG = 20

    def __init__(self, n_vertices):
        self.n = n_vertices
        self.adjacent = [[] for _ in range(self.n)]

    def add_edge(self, u, v, weight=1):
        self.adjacent[u].append((v, weight))
        self.adjacent[v].append((u, weight))

    def dfs(self, source, c_parent, c_level, c_length):
        # Search from the source down the tree and set parent, level, length accordingly.
        self.parent[source] = c_parent
        self.level[source] = c_level
        self.length[source] = c_length
        for child, weight in self.adjacent[source]:
            if child != c_parent:
                self.dfs(child, source, c_level + 1, c_length + weight)

    def build(self, root):
        # Once edges are added, build the tree/data structure.
        self.parent = [None]*self.n
        self.level = [None]*self.n
        self.length = [None]*self.n
        self.dfs(root, -1, 0, 0)
        self.ancestor = [[-1]*self.MAX_LOG for _ in range(self.n)]
        # Initial step: ancestor[v][0] = parent[v]
        for v in range(self.n):
            self.ancestor[v][0] = self.parent[v]
        # Now, compute ancestor[v][k] from 1->MAX_LOG
        for k in range(1, self.MAX_LOG):
            for v in range(self.n):
                if self.ancestor[v][k-1] != -1:
                    # Move 2^{k-1} up, then 2^{k-1} again.
                    self.ancestor[v][k] = self.ancestor[self.ancestor[v][k-1]][k-1]

    def query(self, u, v, root=None):
        # What is the lowest common ancestor of u, v?
        # Extension: Make this query from any root vertex you want.
        if root is not None:
            # Custom root -- see diagrams below for reasoning.n
            a = self.query(u, v)n
            b = self.query(u, root)n
            c = self.query(v, root)n
            # Case 1: root is in the same component as u when `a` is removed from the tree. So `b` is the LCAn
            if (a == c and c != b) return bn
            # Case 2: root is in the same component as v when `a` is removed from the tree. So `a` is the LCAn
            if (a == b and c != b) return cn
            # Case 3: b and c are above a in the tree. So return an
            return an
        # assume that u is higher up than v, to simplify the code below
        if self.level[u] > self.level[v]:
            u, v = v, u
        # STEP 1: set u and v to be ancestors with the same level
        for k in range(self.MAX_LOG-1, -1, -1):
            if (self.level[v] - (1 << k) >= self.level[u]):
                # If v is 2^k levels below u, move it up 2^k levels.
                v = self.ancestor[v][k]
        # We can be certain that level[u] = level[v]. Reason: binary representation of all natural numbers.
        # Do we need to move to step 2?
        if (u == v): return u
        # STEP 2: find the highest ancestor where u != v. Then the parent is the LCA
        for k in range(self.MAX_LOG-1, -1, -1):
            if (self.ancestor[u][k] != self.ancestor[v][k]):
                # Move up 2^k steps
                u = self.ancestor[u][k]
                v = self.ancestor[v][k]
        return self.parent[u]

    def dist(self, u, v):
        # Find the distance between two vertices

        return self.length[u] + self.length[v] - 2 * self.length[self.query(u, v)]n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

template<typename T = int> struct LCA {
    // vertices are represented as numbers 0->n-1.
    // number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6.
    int MAX_LOG = 20;
    int n; vector<vector<pair<int, T> > > adjacent;
    vi parent, level;
    vvi ancestor;
    vector<T> length;

    LCA(int n_vertices) : n(n_vertices), adjacent(n), parent(n), level(n), length(n) { }

    void add_edge(int u, int v, T weight=1) {
        adjacent[u].emplace_back(v, weight);
        adjacent[v].emplace_back(u, weight);
    }

    void dfs(int source, int c_parent, int c_level, T c_length) {
        // Search from the source down the tree and set parent, level, length accordingly.
        parent[source] = c_parent;
        level[source] = c_level;
        length[source] = c_length;
        for (auto v: adjacent[source])
            if (v.first != c_parent)
                dfs(v.first, source, c_level+1, c_length+v.second);
    }

    void build(int root=0) {
        // Once edges are added, build the tree/data structure.
        dfs(root, -1, 0, 0);
        // Compute ancestor
        ancestor.assign(n, vi(MAX_LOG, -1));
        // Initial step: ancestor[v][0] = parent[v]
        for (int v=0; v<n; v++)
            ancestor[v][0] = parent[v];
        // Now, compute ancestor[v][k] from 1->MAX_LOG
        for (int k=1; k < MAX_LOG; k++)
            for (int v=0; v<n; v++)
                if (ancestor[v][k-1] != -1) {
                    // Move 2^{k-1} up, then 2^{k-1} again.
                    ancestor[v][k] = ancestor[ancestor[v][k-1]][k-1];
                }
    }

    int query(int u, int v, int root=-1) {
        // What is the lowest common ancestor of u, v?
        // Extension: Make this query from any root vertex you want.
        if (root != -1) {
            // Custom root -- see diagrams below for reasoning.n
            int a = query(u, v);n
            int b = query(u, root);n
            int c = query(v, root);n
            // Case 1: root is in the same component as u when `a` is removed from the tree. So `b` is the LCAn
            if (a == c and c != b) return b;n
            // Case 2: root is in the same component as v when `a` is removed from the tree. So `a` is the LCAn
            if (a == b and c != b) return c;n
            // Case 3: b and c are above a in the tree. So return an
            return a;n
        }
        // assume that u is higher up than v, to simplify the code below
        if (level[u] > level[v]) swap(u, v);
        // STEP 1: set u and v to be ancestors with the same level
        for (int k=MAX_LOG-1, k>=0; k--)
            if (level[v] - (1 << k) >= level[u]) {
                // If v is 2^k levels below u, move it up 2^k levels.
                v = ancestor[v][k];
            }
        // We can be certain that level[u] = level[v]. Reason: binary representation of all natural numbers.
        // Do we need to move to step 2?
        if (u == v) return u
        // STEP 2: find the highest ancestor where u != v. Then the parent is the LCA
        for (int k=MAX_LOG; k>=0; k--)
            if (ancestor[u][k] != ancestor[v][k]) {
                // Move up 2^k steps
                u = ancestor[u][k];
                v = ancestor[v][k];
            }
        return parent[u];
    }

    T dist(int u, int v) {
        // Find the distance between two vertices
        return length[u] + length[v] - 2 * length[query(u, v)];n
    }
}

And that’s our implementation done! Now get out there and solve some problems!

Related Problems

Data Structures, Trees
Difficulty 3
This post is licensed under GNU GPL V3 by the author.
Recent Update
Trending Tags
Difficulty 3 Difficulty 2
Contents

Primes and Factorization Techniques

Challenge Problems - 2021 Sem 2, Contest 1

Comments powered by Disqus.