heavy path decomposition

目的

頂点数$n$の木を、heavy path decompositionという方法でパスに分解します。パスをつぶすと高さは$O(\log n)$になります。各パスをデータ構造で管理することで、任意のパスに対するクエリに答えることができます。 下記の実装では頂点に重みをつけており、任意頂点間のパスに含まれる頂点の重みの最大値を$O((\log n)^2)$で計算します。各パスにはセグメント木を載せています。

計算量

$O(n)$ (heavy path decomposition単体の計算量)

使い方

public HLDecomposition(int n)
頂点数nの木のheavy path decompositionのコンストラクタです。
void ae(int a, int b)
頂点a,b間に辺を張ります。
void pre()
heavy path decompositonを行います。
int[] heavy
頂点iと子頂点jを結ぶ辺がheavy pathとなるとき、heavy[i]=jとなります。
void setVal(int k, int val)
頂点kに重みvalを設定します。
long output(int a, int b, HLDecomposition hl, SegmentTree st)
heavy path decompositionがhl,頂点の重みがstで与えられるような木について、頂点a,b間のパスに含まれる頂点の重みのうち最大のものをreturnします。
int lca(int u, int v)
頂点vと頂点vの最近接共通祖先をreturnします。

ソースコード

long output(int a, int b, HLDecomposition hl, SegmentTree st) {
	long ea = -1;
	long eb = -1;
	while (hl.head[a] != hl.head[b]) {
		if (hl.depth[hl.head[a]] < hl.depth[hl.head[b]]) {
			int tmp = a;
			a = b;
			b = tmp;
			long tmp_e = ea;
			ea = eb;
			eb = tmp_e;
		}
		ea = merge(st.query(hl.id[hl.head[a]], hl.id[a] + 1), ea);
		a = hl.parent[hl.head[a]];
	}
	if (hl.depth[a] < hl.depth[b]) {
		int tmp = a;
		a = b;
		b = tmp;
		long tmp_e = ea;
		ea = eb;
		eb = tmp_e;
	}
	return merge(eb, merge(st.query(hl.id[b], hl.id[a] + 1), ea));
}

long merge(long a, long b) {
	return Math.max(a, b);
}

class SegmentTree {
	int n;
	long[] Vs;

	public SegmentTree(int n_) {
		n = 1;
		while (n < n_) {
			n *= 2;
		}
		Vs = new long[2 * n - 1];
		for (int i = 0; i < n; ++i) {
			Vs[i + n - 1] = -1;
		}
		for (int i = n - 2; i >= 0; --i) {
				Vs[i] = merge(Vs[2 * i + 1], Vs[2 * i + 2]);
			}
		}

	void setVal(int k, long val) {
		k += n - 1;
		if (val != -1)
			Vs[k] = val;
		else 
			Vs[k] = -1;
		while (k > 0) {
			k = (k - 1) / 2;
			Vs[k] = merge(Vs[2 * k + 1], Vs[2 * k + 2]);
		}
	}

	long query(int a, int b) {
		return query(a, b, 0, n, 0);
	}

	long query(int a, int b, int l, int r, int k) {
		if (b <= l || r <= a) {
			return -1L;
		}
		if (a <= l && r <= b) {
			return Vs[k];
		} else  {
			long vl = query(a, b, l, (l + r) / 2, 2 * k + 1);
			long vr = query(a, b, (l + r) / 2, r, 2 * k + 2);
			return merge(vl, vr);
		}
	}
}

class HLDecomposition {
	int n;
	int[] depth;
	int[] head;
	int[] heavy;
	int[] parent;
	int[] sz;
	ArrayList<Integer>[] g;
	int[] id;

	@SuppressWarnings("unchecked")
	public HLDecomposition(int n) {
		this.n = n;
		depth = new int[n];
		head = new int[n];
		heavy = new int[n];
		parent = new int[n];
		id = new int[n];
		sz = new int[n];
		g = new ArrayList[n];
		for (int i = 0; i < n; ++i) {
			g[i] = new ArrayList<>();
		}
		Arrays.fill(head, -1);
		Arrays.fill(id, -1);
		Arrays.fill(parent, -1);
		Arrays.fill(heavy, -1);
	}

	void ae(int a, int b) {
		g[a].add(b);
		g[b].add(a);
	}

	void pre() {
		dfs(0, -1);
		bfs();
	}

	void bfs() {
		ArrayDeque<Integer> pend = new ArrayDeque<>();
		int gen = 0;
		pend.add(0);
		while (!pend.isEmpty()) {
			int v = pend.pollFirst();
			int top = v;
			for (; v != -1; v = heavy[v]) {
				id[v] = gen++;
				head[v] = top;
				for (int d : g[v]) {
					if (d == parent[v] || d == heavy[v]) {
						continue;
					}
					pend.add(d);
				}
			}
		}
	}

	int lca(int u, int v) {
		if (head[u] != head[v]) {
			if (depth[head[u]] < depth[head[v]]) {
				int tmp = u;
				u = v;
				v = tmp;
			}
			return lca(parent[head[u]], v);
		} else  {
		if (depth[u] > depth[v]) {
			int tmp = u;
				u = v;
				v = tmp;
			}
			return u;
		}
	}

	int dfs(int c, int p) {
		parent[c] = p;
		int s = 1;
		for (int d : g[c]) {
			if (d == p)
				continue;
			depth[d] = depth[c] + 1;
			s += dfs(d, c);
		}
		sz[c] = s;
		for (int d : g[c])
			if (sz[d] * 2 >= sz[c]) {
				heavy[c] = d;
			}
		return s;
	}
	
}