树链剖分模板

本篇对应源码见仓库 solutions/xcpc/algorithm/graph/hld/。

树链剖分模板

struct HLD {
	int n, cnt;
	vector<vector<int>> adj;
	vector<int> fa, dep, sz, top, in, out, seq;

	HLD(int _n) {
		init(_n);
	}

	void init(int _n) {
		n = _n;
		cnt = 0;
		adj.resize(n);
		fa.resize(n);
		dep.resize(n);
		sz.resize(n);
		top.resize(n);
		in.resize(n); out.resize(n);
		seq.resize(n);
	}

	void add(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	// fa, dep, sz, son
	void dfs1(int u) {
		if(fa[u] != -1) adj[u].erase(find(all(adj[u]), fa[u]));

		sz[u] = 1;
		for(auto &v : adj[u]) {
			fa[v] = u;
			dep[v] = dep[u] + 1;
			dfs1(v);
			sz[u] += sz[v];
			if(sz[v] > sz[adj[u][0]]) {
				swap(v, adj[u][0]);
			}
		}
	}

	// in, seg, top
	void dfs2(int u) {
		in[u] = cnt++;
		seq[in[u]] = u;
		for(auto v : adj[u]) {
			top[v] = top[v] == adj[u][0] ? top[u] : v;
			dfs2(v);
		}
		out[u] = cnt;
	}

	int lca(int u, int v) {
		while(top[u] != top[v]) {
			if(dep[top[u]] > dep[top[v]]) {
				u = fa[top[u]];
			} else {
				v = fa[top[v]];
			}
		}
		return dep[u] < dep[v] ? u : v;
	}

	int dis(int u, int v) {
		return dep[u] + dep[v] - 2 * dep[lca(u, v)];
	}
	// 查询 u 的第 k 级祖先
	int jump(int u, int k) {
		if(dep[u] < k) {
			return -1;
		}
		int d = dep[u] - k;
		while(dep[top[u]] > d) {
			u =fa[top[u]];
		}
		return seq[in[u] - (dep[u] - d)];
	}

	// 判断 u 为 v 的祖先
	bool isAncester(int u, int v ){
		return in[u] <= in[v] && in[v] < out[u];
	}
};