mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

Lowest Common Ancestor
(graph/lowest_common_ancestor.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "graph/lowest_common_ancestor.hpp"

Lowest Common Ancestor

使い方

lowest_common_ancestor(vector<vector<int>> g, int root) : $root$ を 根とする木の LCA を求めるためのコンストラクタ。 $O(N \log N)$ get(int u, int v) : 頂点 $u, v$ の $LCA$ を求める。 $O(\log N)$

Verified with

• verify/aoj/grl/5_C.test.cpp
• verify/yosupo/lca.test.cpp

Code

#pragma once

#include<vector>

struct lowest_common_ancestor {
private:
	int n;
	int root;
	std::vector<std::vector<int>>par;
public:
	std::vector<int>depth;

	lowest_common_ancestor(std::vector<std::vector<int>>& g, int Root) : n((int)g.size()) {
		depth.resize(n);
		par.resize(n);
		for (int i = 0; i < n; i++)par[i].resize(31);
		root = Root;

		auto dfs = [&](auto f, int v, int p, int d) -> void {
			par[v][0] = p;
			depth[v] = d;
			for(size_t i = 0;i < g[v].size();i++){
				if(g[v][i] == p)continue;
				f(f, g[v][i], v, d+1);
			}
		};

		dfs(dfs, root, -1, 0);
		
		for (int i = 0; i < 30; i++) {
			for (int j = 0; j < n; j++) {
				if (par[j][i] == -1)par[j][i + 1] = -1;
				else par[j][i + 1] = par[par[j][i]][i];
			}
		}
	}

	int get(int u, int v) {
		if (depth[u] > depth[v])std::swap(u, v);
		for (int i = 30; i >= 0; i--) {
			if (((depth[v] - depth[u]) >> i) & 1) {
				v = par[v][i];
			}
		}
		if (u == v)return u;

		for (int i = 30; i >= 0; i--) {
			if (par[u][i] != par[v][i]) {
				u = par[u][i];
				v = par[v][i];
			}
		}
		return par[u][0];
	}
};

#line 2 "graph/lowest_common_ancestor.hpp"

#include<vector>

struct lowest_common_ancestor {
private:
	int n;
	int root;
	std::vector<std::vector<int>>par;
public:
	std::vector<int>depth;

	lowest_common_ancestor(std::vector<std::vector<int>>& g, int Root) : n((int)g.size()) {
		depth.resize(n);
		par.resize(n);
		for (int i = 0; i < n; i++)par[i].resize(31);
		root = Root;

		auto dfs = [&](auto f, int v, int p, int d) -> void {
			par[v][0] = p;
			depth[v] = d;
			for(size_t i = 0;i < g[v].size();i++){
				if(g[v][i] == p)continue;
				f(f, g[v][i], v, d+1);
			}
		};

		dfs(dfs, root, -1, 0);
		
		for (int i = 0; i < 30; i++) {
			for (int j = 0; j < n; j++) {
				if (par[j][i] == -1)par[j][i + 1] = -1;
				else par[j][i + 1] = par[par[j][i]][i];
			}
		}
	}

	int get(int u, int v) {
		if (depth[u] > depth[v])std::swap(u, v);
		for (int i = 30; i >= 0; i--) {
			if (((depth[v] - depth[u]) >> i) & 1) {
				v = par[v][i];
			}
		}
		if (u == v)return u;

		for (int i = 30; i >= 0; i--) {
			if (par[u][i] != par[v][i]) {
				u = par[u][i];
				v = par[v][i];
			}
		}
		return par[u][0];
	}
};

Back to top page