树链剖分

我们一般使用重链剖分，就是子树大的先剖分，应为这样可以保证时间在 \(log_n\)

如图，先按照 \(dfs\) 序遍历出有一棵树，那么 \(dfs\) 序就是 \([1, 2, 3, 4, 5, 6, 7, 8, 9]\)，如果碰到一条边上 \(dfn[f] - dfn[u] != 1\) 则断一次，就可以剖出链了，如图，链为 \([1, 2, 3] [4, 5] [6, 7, 8] [9]\)，接下来我们还要维护两个东西，分别是 \(top_i\) 表示包含 \(i\) 的链的顶点，和 \(fa_i\) 表示 i 的父亲，代码:

void dfs1(int u, int f) {
	fa[u] = f;
	sz[u] = 1;
	for (auto v : g[u]) {
		if (v != f) {
			dfs1(v, u);
			sz[u] += sz[v];
			if (sz[son[u]] < sz[v]) son[u] = v;
		}
	}
}

void dfs2(int u, int f) {
	dfn[u] = ++dcnt;
	if (son[u]) {
		top[son[u]] = top[u];
		dfs2(son[u], u);
	} 
	for (auto v : g[u]) {
		if (v != son[u] && v != f) {
			top[v] = v;
			dfs2(v, u);
		}
	}
}

int main() {
	dfs1(root, 0);
	top[root] = root;
	dfs2(root, 0);
}

如果要找到 \(u\) 到根节点的路径可以参考以下代码:

int u = x;
while (top[u] != top[root]) {
	cout << u << " -> " << top[u] << " -> " << fa[top[u]];
	u = fa[top[u]];
}
cout << u << " -> " << v;

如果要找到 \(u\) 到 \(v\) 的 \(lca\) 可以参考如下代码:

int lca(int u, int v) {
	int ans = 0;
	while (top[u] != top[v]) {
		if (dfn[u] < dfn[v]) {
			swap(u, v);
		}
		u = fa[top[u]];
	}
	if (dfn[u] < dfn[v]) {
		return u;
	}
	return v;
}