好久没有写博客了，联赛前一天来写一点关于LCA的各种模板 极力推荐第四种方法
把树按照DFS序重新编号并求出DFS序列后，利用序列中两点编号之间的最小值即为LCA的性质，通过RMQ求解。 代码如下：
/* ID: Sunshine_cfbsl LANG: C++ PROG: LCA */ #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int MAXN = 500010; int n, m, s, fp[MAXN], id[MAXN], pn, an, dp[MAXN*2][21]; int Begin[MAXN], to[MAXN*2], Next[MAXN*2], e; inline int read() { int x = 0; char ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x; } inline void Add(int u, int v) { to[++e] = v; Next[e] = Begin[u]; Begin[u] = e; } void dfs(int u, int f) { int i, c; id[c = ++pn] = u; dp[fp[u] = ++an][0] = c; for(i = Begin[u]; i; i = Next[i]) { if(to[i] == f) continue; dfs(to[i], u); dp[++an][0] = c; } } void Sparse_Table() { int i, j; for(j = 1; (1<<j) <= an; j++) for(i = 1; i+(1<<j)-1 <= an; i++) dp[i][j] = min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); } inline int LCA(int l, int r) { int i, k = (int) (log(r-l+1)/log(2)); return id[min(dp[l][k], dp[r-(1<<k)+1][k])]; } int main() { int i, u, v; n = read(); m = read(); s = read(); for(i = 1; i < n; i++) { u = read(); v = read(); Add(u, v); Add(v, u); } dfs(s, -1); Sparse_Table(); for(i = 1; i <= m; i++) { u = read(); v = read(); if(fp[u] > fp[v]) swap(u, v); printf("%d\n", LCA(fp[u], fp[v])); } return 0; }如果这里用链式前向星存树，它比邻接表要快一些。 时间复杂度 O(n+nlog2n+m)
Tarjan算法是一种离线算法，预先把所有的询问存储，再一遍DFS配合并查集解决所有询问，这里不进行详细介绍。 代码如下：
/* ID: Sunshine_cfbsl LANG: C++ PROG: LCA */ #include<cstdio> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int MAXN = 500010; int n, m, s, fa[MAXN], ans[MAXN]; int Begin[MAXN], to[MAXN*2], Next[MAXN*2], e; bool done[MAXN]; struct Query { int v, id; Query(int v, int id): v(v), id(id) {} }; vector<Query> q[MAXN]; inline int read() { int x = 0; char ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x; } inline void Add(int u, int v) { to[++e] = v; Next[e] = Begin[u]; Begin[u] = e; } int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]); } void Tarjan(int u, int f) { fa[u] = u; int i; for(i = Begin[u]; i; i = Next[i]) { if(to[i] == f) continue; Tarjan(to[i], u); fa[find(to[i])] = u; } done[u] = true; for(i = 0; i < q[u].size(); i++) if(done[q[u][i].v]) ans[q[u][i].id] = find(q[u][i].v); } int main() { int i, u, v; n = read(); m = read(); s = read(); for(i = 1; i < n; i++) { u = read(); v = read(); Add(u, v); Add(v, u); } for(i = 1; i <= m; i++) { u = read(); v = read(); q[u].push_back(Query(v, i)); q[v].push_back(Query(u, i)); } Tarjan(s, -1); for(i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0; }该算法比ST算法要快一些，但有一定的局限性。 时间复杂度 O(n+m+nα(n))
树上倍增是一种功能强大的算法，它不仅能够实现求LCA，还能够实现许多其他的功能，许多跟树有关的中等难度的题目都跟它有关。 同样是运用了类似RMQ的倍增思想，fa[i][j]表示节点i的 2j 级祖先，先dfs一遍求出fa[i][0]和每个节点的深度，再用类似RMQ的写法求出整个fa[][]数组。 求LCA时先把较深的节点提到和另一节点同一深度，然后让两个节点同时上升，直至两个节点父亲相同，则该父亲即为答案。 代码如下：
/* ID: Sunshine_cfbsl LANG: C++ PROG: LCA */ #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int MAXN = 500010; int n, m, s, b, dep[MAXN], maxd, fa[MAXN][20]; int Begin[MAXN], to[MAXN*2], Next[MAXN*2], e; inline int read() { int x = 0; char ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x; } inline void Add(int u, int v) { to[++e] = v; Next[e] = Begin[u]; Begin[u] = e; } void dfs(int u) { if(fa[u][0] != -1) maxd = max(maxd, dep[u] = dep[fa[u][0]]+1); int i; for(i = Begin[u]; i; i = Next[i]) { if(to[i] == fa[u][0]) continue; fa[to[i]][0] = u; dfs(to[i]); } } void Doubling() { int i, j; for(j = 1; j <= b; j++) for(i = 1; i <= n; i++) if(fa[i][j-1] != -1) fa[i][j] = fa[fa[i][j-1]][j-1]; } int LCA(int u, int v) { int i, j; if(dep[u] < dep[v]) swap(u, v); for(j = b; j >= 0; j--) if(fa[u][j] != -1 && dep[fa[u][j]] >= dep[v]) u = fa[u][j]; if(u == v) return v; for(j = b; j >= 0; j--) if(fa[u][j] != fa[v][j]) { u = fa[u][j]; v = fa[v][j]; } return fa[u][0]; } int main() { int i, u, v; n = read(); m = read(); s = read(); memset(fa, -1, sizeof(fa)); for(i = 1; i < n; i++) { u = read(); v = read(); Add(u, v); Add(v, u); } dfs(s); b = (int) (log(maxd)/log(2)); Doubling(); for(i = 1; i <= m; i++) { u = read(); v = read(); printf("%d\n", LCA(u, v)); } return 0; }该算法时间复杂度为 O(n+nlog2d+mlog2d) ，d在最坏情况下等于n，但由于这种情况出现较少，如果是一棵比较平衡的树，一般比前两种算法要快一些。
该方法是由LYQ（罗大神！）由树链剖分加以改进而发明的算法（但他本人并没有在博客中写到），虽然是树链剖分，但是远没有原版树链剖分复杂。在某个评测网站上经过裸题测试之后发现虽然复杂度相差不远，但由于常数较小，比以上三种算法都要快，并且代码并不复杂。 树链剖分戳这里 我们只需要进行一次DFS求得dep[];size[];fa[];top[]（其中top[]在DFS之后等价与fa[]）四个数组，然后每次查询时，通过类似并查集的方法，使得top[]实现原来在树链剖分中的功能。 具体见代码：
/* ID: Sunshine_cfbsl LANG: C++ PROG: LCA */ #include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int MAXN = 500010; int n, m, s, dep[MAXN], fa[MAXN], top[MAXN], size[MAXN]; int Begin[MAXN], to[MAXN*2], Next[MAXN*2], e; inline int read() { int x = 0; char ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x; } inline void Add(int u, int v) { to[++e] = v; Next[e] = Begin[u]; Begin[u] = e; } void dfs(int u) { int i, maxs = 0, son = 0; top[u] = u; size[u] = 1; for(i = Begin[u]; i; i = Next[i]) { if(to[i] == fa[u]) continue; fa[to[i]] = u; dep[to[i]] = dep[u]+1; dfs(to[i]); size[u] += size[to[i]]; if(size[to[i]] > maxs) maxs = size[son = to[i]]; } if(son) top[son] = u; } int find(int u) { return top[u] = top[u] == u ? u : find(top[u]); } int LCA(int u, int v) { if(find(u) != find(v)) return dep[top[u]] > dep[top[v]] ? LCA(fa[top[u]], v): LCA(u, fa[top[v]]); else return dep[u] > dep[v] ? v : u; } int main() { int i, u, v; n = read(); m = read(); s = read(); memset(fa, -1, sizeof(fa)); for(i = 1; i < n; i++) { u = read(); v = read(); Add(u, v); Add(v, u); } dfs(s); for(i = 1; i <= m; i++) { u = read(); v = read(); printf("%d\n", LCA(u, v)); } return 0; }时间复杂度最坏估计 O(n+mlog2n)
