最近公共祖先

基本原理

求解树上两节点的最近公共祖先，有暴力递推法和倍增法，但基本原理差不多，即从两节点向上搜索父节点直至相遇即可找到最近公共祖先，但如果实现搜索一遍树结构，保存所有节点的父节点情况，再进行lca搜索可以大大节省时间，这就是基本的思路。实际上，该算法有固定模板，做题时记好模板即可。

流程

模板

void dfs(int u, int father) {
dep[u] = dep[father] + 1;
for (int i = 1; (1 << i) <= dep[u]; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (auto v : g[u]) {
if (v == father)continue;
f[v][0] = u;
dfs(v, u);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y])swap(x, y);
for (int i = 20; i >= 0; i–) {
if (dep[f[x][i]] >= dep[y])x = f[x][i];
if (x == y)return x;
}
for (int i = 20; i >= 0; i–) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}

注意细节

倍增算法复杂度O(logn)
常与树形dp/树上差分相结合