LCA

tree/lca.hpp · GitHub で見る

共通ページ

根付き木の 2 頂点に対し、両方の祖先で最も深い頂点を求めます。add_edge で木の辺を全て追加し、build を呼んでから問い合わせます。

#include "lib/tree/lca.hpp"

LCA tree(3);
tree.add_edge(0, 1);
tree.add_edge(1, 2);
tree.build();
int v = tree.lca(0, 2); // 0
int distance = tree.dist(0, 2); // 2
auto [l, r] = tree.subtree(1);
int count = r - l; // 2

操作	内容・返り値	計算量
LCA(n = 0)	頂点数を指定	\(O(n)\)
add_edge(u,v)	無向辺を追加し、辺 ID を返す	償却 \(O(1)\)
build(root = 0)	指定した根で前処理	\(O(n\log n)\)
build_from_parents(parents)	親配列から木を構築して前処理	\(O(n\log n)\)
lca(u,v)	最小共通祖先	\(O(1)\)
dist(u,v)	経路の辺数	\(O(1)\)
is_ancestor(u,v)	u が v の祖先か。自身も含む	\(O(1)\)
subtree(v)	DFS の行きがけ順での部分木の半開区間 [l,r)。l は v の位置	\(O(1)\)
parent[v] / depth[v]	親（根は -1）／根からの辺数	\(O(1)\)
n / edges[id]	全頂点数／辺の両端	\(O(1)\)

無向木を扱い、0 <= n <= INT_MAX/2、頂点番号は [0,n) とします。build(root = 0) で根を指定します。空の木では頂点を指定する問い合わせはできません。公開の n・辺・親・深さは直接書き換えないでください。

親配列がある場合は build_from_parents(std::vector<int> parents) を使えます。頂点数は配列の長さとなり、根の親を -1、それ以外の親を [0,n) の頂点番号で指定します。根はちょうど 1 頂点で、全頂点が根につながる木である必要があります。頂点番号は任意の順序で構いません。空配列も渡せます。

#include "lib/tree/lca.hpp"

LCA rooted;
rooted.build_from_parents({-1, 0, 1});
int ancestor = rooted.lca(1, 2); // 1

既存の頂点・辺は置き換わります。edges には根以外の頂点 v の (parents[v], v) が v の昇順で入り、その順番が辺 ID になります。配列を以降使わない場合は build_from_parents(std::move(parents)) と渡せます。

subtree(v) の区間は、元の頂点番号の区間ではありません。根から DFS して初めて訪れる順に各頂点へ番号を付けたとき、v とその子孫が占める区間 [l,r) です。l が v 自身の DFS 番号、r-l が v を含む部分木の頂点数です。

辺を追加する段階で閉路のない連結な木にし、空でなければ辺数を n-1 にしてください。辺や根を変えた後は build を呼び直します。距離は重みの合計ではなく辺数です。

前処理・空間計算量は \(O(n \log n)\)、各クエリは \(O(1)\) です。

依存ライブラリ

• Default Init Allocator
• Static Range Min
• Sparse Table

検証コード

• test/auxiliary_tree.test.cpp
• test/lca_path_sum.test.cpp
• test/lowest_common_ancestor.test.cpp

コード

#ifndef LCA_HPP
#define LCA_HPP

#include "../components/static_range_min.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <utility>
#include <vector>

class LCA {
	std::vector<int> in, out, order;
	bool ordered_ = false;
	StaticRangeMin<int, true> table;
	void check([[maybe_unused]] int v) const { assert(0 <= v && v < n && static_cast<int>(in.size()) == n); }

	void finish(int root) {
		in[root] = n;
		ordered_ = root == 0;
		for (int i = n - 2; i >= 0; --i) {
			int v = order[i], p = parent[v];
			depth[v] = depth[p] + 1;
			in[v] = in[p];
			in[p] -= out[v];
		}
		for (int v = 0; v < n; ++v) {
			--in[v];
			out[v] += in[v];
			order[in[v]] = v;
			ordered_ &= parent[v] < v;
		}
		std::vector<int> values(n);
		for (int i = 1; i < n; ++i) values[i] = ordered_ ? parent[order[i]] : in[parent[order[i]]];
		table.build(std::move(values));
		parent[root] = -1;
	}

  public:
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> parent, depth;
	explicit LCA(int n = 0) : n(n) {
		assert(0 <= n && n <= std::numeric_limits<int>::max() / 2);
		edges.reserve(std::max(0, n - 1));
	}
	int add_edge(int u, int v) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		edges.emplace_back(u, v);
		return static_cast<int>(edges.size()) - 1;
	}
	void build(int root = 0) {
		assert(n >= 0 && edges.size() == std::size_t(std::max(0, n - 1)));
		assert(!n || (0 <= root && root < n));
		in.resize(n);
		out.resize(n);
		order.resize(n);
		parent.assign(n, -1);
		depth.assign(n, 0);
		table = StaticRangeMin<int, true>();
		if (!n) return;
		std::vector<int> degree(n), neighbors(n);
		for (auto [u, v] : edges) {
			++degree[u], ++degree[v];
			neighbors[u] ^= v, neighbors[v] ^= u;
		}
		degree[root] += 2;
		std::fill(out.begin(), out.end(), 1);
		int count = 0;
		for (int v = 0; v < n; ++v) if (degree[v] == 1) order[count++] = v;
		for (int i = 0; i < count; ++i) {
			int v = order[i], p = neighbors[v];
			parent[v] = p;
			out[p] += out[v];
			neighbors[p] ^= v;
			if (--degree[p] == 1) order[count++] = p;
		}
		assert(count == n - 1);
		finish(root);
	}

	void build_from_parents(std::vector<int> parents) {
		assert(parents.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
		n = static_cast<int>(parents.size());
		parent = std::move(parents);
		in.resize(n);
		out.assign(n, 1);
		order.resize(n);
		depth.assign(n, 0);
		table = StaticRangeMin<int, true>();
		edges.clear();
		edges.reserve(std::max(0, n - 1));
		if (!n) return;
		int root = -1;
		bool ordered = true;
		for (int v = 0; v < n; ++v) {
			int p = parent[v];
			assert(-1 <= p && p < n && p != v);
			if (p == -1) {
				assert(root == -1);
				root = v;
			} else {
				edges.emplace_back(p, v);
				ordered &= p < v;
			}
		}
		assert(root != -1);
		if (ordered) {
			for (int v = n - 1; v > 0; --v) {
				out[parent[v]] += out[v];
				order[n - 1 - v] = v;
			}
		} else {
			std::fill(in.begin(), in.end(), 0);
			for (int v = 0; v < n; ++v) if (v != root) ++in[parent[v]];
			int count = 0;
			for (int v = 0; v < n; ++v) if (!in[v] && v != root) order[count++] = v;
			for (int i = 0; i < count; ++i) {
				int v = order[i], p = parent[v];
				out[p] += out[v];
				if (!--in[p] && p != root) order[count++] = p;
			}
			assert(count == n - 1);
		}
		finish(root);
	}

	int lca(int u, int v) const {
		check(u);
		check(v);
		int l = in[u], r = in[v];
		if (l == r) return u;
		if (l > r) std::swap(l, r);
		++l;
		int w = table.prod(l, r + 1);
		return ordered_ ? w : order[w];
	}
	int dist(int u, int v) const {
		int w = lca(u, v);
		return depth[u] + depth[v] - 2 * depth[w];
	}
	bool is_ancestor(int u, int v) const {
		check(u);
		check(v);
		return in[u] <= in[v] && in[v] < out[u];
	}
	std::pair<int, int> subtree(int v) const {
		check(v);
		return {in[v], out[v]};
	}
};

#endif

Back to top page