graph/tree/LCA.hpp

• View this file on GitHub
• Last update: 2026-08-24 20:36:44+07:00
• Include: #include "graph/tree/LCA.hpp"

Depends on

• graph/Graph.hpp

Verified with

• test/1_library_checker/graph/LCA.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>
#include "graph/Graph.hpp"

template <typename T = int>
class LCA {
	int n, LOG;
	std::vector<std::vector<int>> up;
	std::vector<int> depth;
	void dfs(const Graph<T> &G, int v, int p, int d) {
                depth[v] = d;
		up[v][0] = p;
		for (int u : G[v]) {
                        if (u != p) {
                                dfs(G, u, v, d + 1);
                        }
		}
	}
public:
        LCA(const Graph<T>& G, int root = 0) {
                n = G.size();
                LOG = 0;
                while ((1 << LOG) <= n) LOG++;
                depth.assign(n, 0);
                up.assign(n, std::vector<int>(LOG, 0));
                dfs(G, root, root, 0);
                for (int i = 1; i < LOG; i++) {
                        for (int v = 0; v < n; v++) {
                                up[v][i] = up[up[v][i - 1]][i - 1];
                        }
                }
        }
	int lift(int v, int k) const {
		for (int j = LOG - 1; j >= 0; j--) {
			if (k & (1 << j)) v = up[v][j];
		}
		return v;
	}
	int query(int u, int v) const {
		if (depth[u] < depth[v]) std::swap(u, v);
		u = lift(u, depth[u] - depth[v]);
		if (u == v) return u;
		for (int j = LOG - 1; j >= 0; j--) {
			if (up[u][j] != up[v][j]) {
				u = up[u][j];
				v = up[v][j];
			}
		}
		return up[v][0];
	}
	int dist(int u, int v) const {
		return depth[u] + depth[v] - 2 * depth[query(u, v)];
	}
};

#line 2 "graph/tree/LCA.hpp"
#include <algorithm>
#include <vector>
#line 3 "graph/Graph.hpp"
#include <cassert>
#include <utility>

template <typename T = int>
struct Edge {
        int from, to;
        T cost;
        int id;
        Edge() : from(-1), to(-1), cost(0), id(-1) {}
        Edge(int _from, int _to, const T& _cost = 1, int _id = -1)
                : from(_from), to(_to), cost(_cost), id(_id) {}
        Edge(int _from, int _to, T&& _cost, int _id = -1)
                : from(_from), to(_to), cost(std::move(_cost)), id(_id) {}
        operator int() const { return to; }
        friend bool operator<(const Edge<T>& lhs, const Edge<T>& rhs) {
                return lhs.cost < rhs.cost;
        }
        friend bool operator>(const Edge<T>& lhs, const Edge<T>& rhs) {
                return lhs.cost > rhs.cost;
        }
};

template <typename T = int>
using Edges  = std::vector<Edge<T>>;

template <typename T = int>
using GMatrix = std::vector<std::vector<T>>;

template <typename T = int>
struct Graph : std::vector<std::vector<Edge<T>>> {
        using Base = std::vector<std::vector<Edge<T>>>;
        using Base::Base;
        int eid = 0;
        int edge_size() const { return eid; }
        int add_edge(int a, int b, const T& c = 1, bool is_directed = false) {
                assert(0 <= a && a < (int)this->size());
                assert(0 <= b && b < (int)this->size());
                (*this)[a].emplace_back(a, b, c, eid);
                if (!is_directed) {
                        (*this)[b].emplace_back(b, a, c, eid);
                }
                return eid++;
        }
};
#line 5 "graph/tree/LCA.hpp"

template <typename T = int>
class LCA {
	int n, LOG;
	std::vector<std::vector<int>> up;
	std::vector<int> depth;
	void dfs(const Graph<T> &G, int v, int p, int d) {
                depth[v] = d;
		up[v][0] = p;
		for (int u : G[v]) {
                        if (u != p) {
                                dfs(G, u, v, d + 1);
                        }
		}
	}
public:
        LCA(const Graph<T>& G, int root = 0) {
                n = G.size();
                LOG = 0;
                while ((1 << LOG) <= n) LOG++;
                depth.assign(n, 0);
                up.assign(n, std::vector<int>(LOG, 0));
                dfs(G, root, root, 0);
                for (int i = 1; i < LOG; i++) {
                        for (int v = 0; v < n; v++) {
                                up[v][i] = up[up[v][i - 1]][i - 1];
                        }
                }
        }
	int lift(int v, int k) const {
		for (int j = LOG - 1; j >= 0; j--) {
			if (k & (1 << j)) v = up[v][j];
		}
		return v;
	}
	int query(int u, int v) const {
		if (depth[u] < depth[v]) std::swap(u, v);
		u = lift(u, depth[u] - depth[v]);
		if (u == v) return u;
		for (int j = LOG - 1; j >= 0; j--) {
			if (up[u][j] != up[v][j]) {
				u = up[u][j];
				v = up[v][j];
			}
		}
		return up[v][0];
	}
	int dist(int u, int v) const {
		return depth[u] + depth[v] - 2 * depth[query(u, v)];
	}
};

Back to top page