该算法可以离线求最近公共祖先，大幅节省时间复杂度（\(O(n \log n)\)->\(O(n+m)\)）。
缺点是如果题目要求强制在线那么就用不了了。
具体实现是这样的：把原树用双向边存起来，然后把每一对要求 LCA 的两个点在一个新图上存一个双向边（称为查询边）。
对原图进行一次 DFS 遍历，遍历过程中使用并查集存储每个节点的祖先。我们在遍历过程中往下遍历时节点的祖先是它本身，遍历完这个节点的子树后回溯时是它的父亲。回溯过程中遍历到以 \(v\) 为根的子树时，如果 \(i\) 节点恰好访问过，而并查集中存储的又正是 \(v\) 的最近祖先，那么 \(v\) 的最近祖先就恰好是两个点的最近公共祖先。将查询边中 \(v\) 到 \(i\) 节点的 LCA 设为并查集中存储 \(v\) 的祖先（即 \(v\) 的父亲）即可。
时间复杂度涉及 \(3\) 个要素，一个是 DFS 的时间复杂度 \(O(n)\)，一个是并查集的初始化 \(O(n)\)，一个是路径压缩优化过后的并查集时间复杂度 \(O(a(n))\)，其中 \(a\) 表示的是阿克曼函数的反函数，增长极其缓慢，常数最大到 \(4\) 左右。总时间复杂度 \(O(n+m)\) 左右。去掉了倍增法的 \(\log\)，但是常数会比倍增法大。
在 LCA 模板题中，可以看到两次提交差别非常大：
在线算法倍增：
离线算法 Tarjan：
可以注意到因为常数较大导致前面的小点跑得反而慢，但是后面的大点快了将近 2 倍。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=5e5+10;
struct Node{int to,nxt,LCA;
}e[2*maxn],q[2*maxn];
int n,m,s,D;
int tot,h[maxn],hq[maxn];
int fa[maxn];
bool vis[maxn];
void Add(int u,int v){tot++;e[tot].to=v;e[tot].nxt=h[u];h[u]=tot;
}
void Addq(int u,int v){tot++;q[tot].to=v;q[tot].nxt=hq[u];hq[u]=tot;
}
int Find(int x){if(fa[x]==x) return x;else return fa[x]=Find(fa[x]);
}
void tarjan(int u){fa[u]=u;vis[u]=1;for(int i=h[u];i!=-1;i=e[i].nxt){int v=e[i].to;if(!vis[v]){tarjan(v);fa[v]=u;}}for(int i=hq[u];i!=-1;i=q[i].nxt){int v=q[i].to;if(vis[v]){if(i%2==0) q[i-1].LCA=q[i].LCA=Find(v);else q[i+1].LCA=q[i].LCA=Find(v);}}
}
int main(){memset(h,-1,sizeof(h));memset(hq,-1,sizeof(hq));scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=n-1;i++){int x,y;scanf("%d%d",&x,&y);Add(x,y);Add(y,x);} tot=0;for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);Addq(a,b);Addq(b,a);}tarjan(s);for(int i=1;i<=2*m;i+=2){printf("%d\n",q[i].LCA);}return 0;
}