LCA Tree
(lca/lca_tree.hpp)

• View this file on GitHub
• Last update: 2025-09-12 21:56:34+09:00
• Include: #include "lca/lca_tree.hpp"

LCA Tree

Overview

The lca_tree is a data structure designed to find the Lowest Common Ancestor (LCA) of any two nodes in a tree. This implementation utilizes the Binary Lifting technique.

Key functionalities include:

• Finding the $k$-th ancestor of a given node.
• Finding the Lowest Common Ancestor (LCA) of two nodes.
• Calculating the distance between two nodes.
• Finding a specific node on the path between two other nodes.

---

Constructor

lca_tree(const std::vector<std::vector<int>>& adj, int root)

• Description: Constructs the lca_tree from an adjacency list adj and a specified root node.
• Constraints:
  • The graph given by adj must be a tree.
  • adj.size() = $N$.
  • $0 \le \text{root} < N$.
• Time Complexity: $O(N \log N)$, where $N$ is the number of nodes.

---

Member Functions

int kth_parent(int u, int k)

• Description: Returns the $k$-th ancestor of node u.
• Constraints:
  • $0 \le u < N$
  • $0 \le k$
• Time Complexity: $O(\log N)$

int lca(int u, int v)

• Description: Returns the Lowest Common Ancestor of nodes u and v.
• Constraints:
  • $0 \le u < N$
  • $0 \le v < N$
• Time Complexity: $O(\log N)$

---

int distance(int u, int v)

• Description: Returns the distance between nodes u and v.
• Constraints:
  • $0 \le u < N$
  • $0 \le v < N$
• Time Complexity: $O(\log N)$

---

int jump(int u, int v, int k)

• Description: Returns the node that is $k$ steps away from u on the simple path to v. If the path length is less than k, it returns -1.
• Constraints:
  • $0 \le u < N$
  • $0 \le v < N$
  • $0 \le k$
• Time Complexity: $O(\log N)$

Verified with

• test/lca_tree.test.cpp
• test/lca_tree_jump.test.cpp

Code

#ifndef LCA_TREE_HPP
#define LCA_TREE_HPP

#include <algorithm>
#include <bit>
#include <cassert>
#include <queue>
#include <vector>

struct lca_tree {
    lca_tree(const std::vector<std::vector<int>> &adj, int root)
        : n_(static_cast<int>(adj.size())), root_(root),
          lg_(std::bit_width(static_cast<unsigned>(n_)) - 1),
          table_((lg_ + 1) * n_), depth_(n_) {
        depth_[root_] = 0;
        table_[root_] = root_;
        std::queue<int> q;
        q.emplace(root_);
        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            for (auto v : adj[u]) {
                if (v != table_[u]) {
                    depth_[v] = depth_[u] + 1;
                    table_[v] = u;
                    q.emplace(v);
                }
            }
        }
        for (auto i = 1; i <= lg_; ++i) {
            for (auto u = 0; u < n_; ++u) {
                auto parent = table_[(i - 1) * n_ + u];
                table_[i * n_ + u] = table_[(i - 1) * n_ + parent];
            }
        }
    }
    int kth_parent(int u, int k) const {
        assert(0 <= u && u < n_ && 0 <= k);
        for (auto i = 0; i <= lg_; ++i) {
            if ((k >> i) & 1) {
                u = table_[i * n_ + u];
            }
        }
        return u;
    }
    int lca(int u, int v) const {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        if (depth_[u] < depth_[v]) {
            std::swap(u, v);
        }
        u = kth_parent(u, depth_[u] - depth_[v]);
        if (u == v) {
            return u;
        }
        for (auto i = lg_; i >= 0; i--) {
            if (table_[i * n_ + u] != table_[i * n_ + v]) {
                u = table_[i * n_ + u];
                v = table_[i * n_ + v];
            }
        }
        return table_[u];
    }
    int distance(int u, int v) const {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        return depth_[u] + depth_[v] - 2 * depth_[lca(u, v)];
    }
    int jump(int u, int v, int k) const {
        assert(0 <= u && u < n_ && 0 <= v && v < n_ && 0 <= k);
        auto l = lca(u, v);
        auto ul = depth_[u] - depth_[l];
        auto vl = depth_[v] - depth_[l];
        if (ul + vl < k) {
            return -1;
        }
        if (k <= ul) {
            return kth_parent(u, k);
        } else {
            return kth_parent(v, ul + vl - k);
        }
    }
    const int n_, root_, lg_;
    std::vector<int> table_, depth_;
};

#endif // LCA_TREE_HPP

#line 1 "lca/lca_tree.hpp"



#include <algorithm>
#include <bit>
#include <cassert>
#include <queue>
#include <vector>

struct lca_tree {
    lca_tree(const std::vector<std::vector<int>> &adj, int root)
        : n_(static_cast<int>(adj.size())), root_(root),
          lg_(std::bit_width(static_cast<unsigned>(n_)) - 1),
          table_((lg_ + 1) * n_), depth_(n_) {
        depth_[root_] = 0;
        table_[root_] = root_;
        std::queue<int> q;
        q.emplace(root_);
        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            for (auto v : adj[u]) {
                if (v != table_[u]) {
                    depth_[v] = depth_[u] + 1;
                    table_[v] = u;
                    q.emplace(v);
                }
            }
        }
        for (auto i = 1; i <= lg_; ++i) {
            for (auto u = 0; u < n_; ++u) {
                auto parent = table_[(i - 1) * n_ + u];
                table_[i * n_ + u] = table_[(i - 1) * n_ + parent];
            }
        }
    }
    int kth_parent(int u, int k) const {
        assert(0 <= u && u < n_ && 0 <= k);
        for (auto i = 0; i <= lg_; ++i) {
            if ((k >> i) & 1) {
                u = table_[i * n_ + u];
            }
        }
        return u;
    }
    int lca(int u, int v) const {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        if (depth_[u] < depth_[v]) {
            std::swap(u, v);
        }
        u = kth_parent(u, depth_[u] - depth_[v]);
        if (u == v) {
            return u;
        }
        for (auto i = lg_; i >= 0; i--) {
            if (table_[i * n_ + u] != table_[i * n_ + v]) {
                u = table_[i * n_ + u];
                v = table_[i * n_ + v];
            }
        }
        return table_[u];
    }
    int distance(int u, int v) const {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        return depth_[u] + depth_[v] - 2 * depth_[lca(u, v)];
    }
    int jump(int u, int v, int k) const {
        assert(0 <= u && u < n_ && 0 <= v && v < n_ && 0 <= k);
        auto l = lca(u, v);
        auto ul = depth_[u] - depth_[l];
        auto vl = depth_[v] - depth_[l];
        if (ul + vl < k) {
            return -1;
        }
        if (k <= ul) {
            return kth_parent(u, k);
        } else {
            return kth_parent(v, ul + vl - k);
        }
    }
    const int n_, root_, lg_;
    std::vector<int> table_, depth_;
};

Back to top page