Info

根付き木をうまく分解することでセグ木などのデータ構造と一緒に部分木クエリやパスに対するクエリが処理できる。ついでにLCA(Lowest Common Ancestor)を\(O(\log{n})\)で求められる。

Complexity

構築 - \(O(n)\)
部分木に対応する区間取得 - \(O(1)\)
2頂点間のパスに対応する区間取得 - \(O(\log{n})\) で \(O(\log{n})\)個の独立な区間を得る
2頂点のLCA - \(O(\log{n})\)

Interface

HLD(n,u_g,root=0) 大きさ\(n\)のグラフu_gに対しrootを根としたdfs木をHLDする
get_subtree(i) 頂点\(i\)の部分木に対応する区間を返す
get_path(a,b) 頂点\(a\),\(b\)間のパスに対応する区間の集合を返す
LCA(a,b) 頂点\(a\),\(b\)のLCAを返す

Code

/* <HLD> */

struct HLD
{
	using Graph = std::vector<std::vector<int> >;
	std::vector<int> sz, in, out, par, nxt;
	Graph g, u_g;
	HLD(int n, Graph& u_g, int root=0)
		: sz(n),in(n),out(n),par(n),nxt(n)
		,g(n,std::vector<int>()), u_g(u_g)
	{
		dfs_tree(root);
		dfs_sz(root);
		dfs_hld(root);
	}
	void dfs_tree(int v,int p=-1) {
		par[v]=p;
		for(int to:u_g[v]) {
			if(to==p) continue;
			g[v].emplace_back(to);
			dfs_tree(to,v);
		}
	}
	void dfs_sz(int v) {
		sz[v]=1;
		for(int& to:g[v]) {
			dfs_sz(to);
			sz[v]+=sz[to];
			if(sz[to]>sz[g[v][0]]) std::swap(to,g[v][0]);
		}
	}
	int t=0;
	void dfs_hld(int v) {
		in[v]=t++;
		for(int to:g[v]) {
			nxt[to] = (to==g[v][0]) ? nxt[v] : to;
			dfs_hld(to);
		}
		out[v]=t;
	}
	int LCA(int a, int b) {
		while(nxt[a]!=nxt[b]) {
			if(in[a]>in[b]) std::swap(a,b);
			b=par[nxt[b]];
		}
		if(in[a]>in[b]) std::swap(a,b);
		return a;
	}
	struct I { int l, r; I(int l, int r) : l(l),r(r) {} };
	I get_subtree(int v) {
		return I(in[v],out[v]);
	}
	std::vector<I> get_path(int a, int b) {
		std::vector<I> intervals;
		while(nxt[a]!=nxt[b]) {
			if(in[a]>in[b]) std::swap(a,b);
			intervals.emplace_back(in[nxt[b]],in[b]+1);
			b=par[nxt[b]];
		}
		if(in[a]>in[b]) std::swap(a,b);
		intervals.emplace_back(in[a],in[b]+1);
		return intervals;
	}
};

/* <HLD> */

Examples

int n=10;
std::vector<std::vector<int> > g(n);
rep(i,n-1) {
    g[i].emplace_back(i+1);
    g[i+1].emplace_back(i);
}
HLD hld(n,g,2);
auto ivs=hld.get_path(0,9);
for(auto e:ivs) std::cout << e.l << ' ' << e.r << EL; // 8 10, 0 8
auto iv=hld.get_subtree(0);
std::cout << iv.l << ' ' << iv.r << EL; // 9 10
iv=hld.get_subtree(2);
std::cout << iv.l << ' ' << iv.r << EL; // 0 10