tree/LCA_kactl.hpp

View this file on GitHub
Last update: 2024-06-26 10:40:27+07:00
Include: #include "tree/LCA_kactl.hpp"

Depends on

Sparse table(KACTL version) (DS/Sparse_table.hpp)

Verified with

test/yosupo/Tree/LCA_yosupo_2.test.cpp

Code

#pragma once
#include "DS/Sparse_table.hpp"
struct LCA {
	int T = 0;
	vi time, path, ret,depth;
	sparsetable<int> rmq;

	LCA(vector<vi>& C) : time(sz(C)), rmq((dfs(C,0,-1), ret)) {}
	void dfs(vector<vi>& C, int v, int par) {
		time[v] = T++;
		for (int y : C[v]) if (y != par) {
			path.push_back(v), ret.push_back(time[v]);
			dfs(C, y, v);
		}
	}

	int lca(int a, int b) {
		if (a == b) return a;
		tie(a, b) = minmax(time[a], time[b]);
		return path[rmq.query(a, b)];
	}
	int dist(int a,int b){return depth[a] + depth[b] - 2*depth[lca(a,b)];}
};

#line 2 "DS/Sparse_table.hpp"

template<class T>
struct sparsetable {
	vector<vector<T>> jmp;
	sparsetable(const vector<T>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= V.size(); pw *= 2, ++k) {
			jmp.emplace_back(V.size() - pw * 2 + 1);
			rep(j,jmp[k].size())
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};
#line 3 "tree/LCA_kactl.hpp"
struct LCA {
	int T = 0;
	vi time, path, ret,depth;
	sparsetable<int> rmq;

	LCA(vector<vi>& C) : time(sz(C)), rmq((dfs(C,0,-1), ret)) {}
	void dfs(vector<vi>& C, int v, int par) {
		time[v] = T++;
		for (int y : C[v]) if (y != par) {
			path.push_back(v), ret.push_back(time[v]);
			dfs(C, y, v);
		}
	}

	int lca(int a, int b) {
		if (a == b) return a;
		tie(a, b) = minmax(time[a], time[b]);
		return path[rmq.query(a, b)];
	}
	int dist(int a,int b){return depth[a] + depth[b] - 2*depth[lca(a,b)];}
};