这个算法在 \(n,m\) 差不多的时候是比较快的，因为他复杂度是 \(O(n+m)\) 的，可惜的是只能离线。

我们对于每一个询问的两点之间连一条无向边（并不是在存树的数组里面连边）

在 DFS 的过程中，给走过的节点打上标记，同时维护并查集，如果 \(u\) 节点的这棵子树没搜完，那么 \(fa[u] = u\);，搜完后再更新并查集。

我们假设查询 \(u\) 和 \(v\) 的最近公共祖先，搜到节点 \(u\)，如果另一个节点 \(v\) 已经被搜到过了，那么 \(v\) 点的并查集祖先就是 \(u\) 和 \(v\) 的最近公共祖先。

我们来模拟一下用 tarjan 求 LCA 的样例

我们在 DFS 的时候，首先来到 \(4\) 号点，然后我们 \(vis[4]=1\)，将两个子节点都合并到 \(4\) 号点上，发现有一组询问 \(4,5\) 但是 \(vis[5]=0\) 所以不能确定 LCA

然后来到 \(2\)，将 \(vis[2]=1\) 发现没法往下走，所以不走了，发现有 \((3,2)\) 和 \((1,2)\) 两组询问，但 \(vis[3]=0\)，\(vis[1]=0\) 所以不能确定 LCA

然后来到 \(1\)，将 \(vis[1]=1\)，将子节点合并到 \(1\) 号点，发现有询问 \((1,2)\)，这个时候 \(vis[2]=1\) 所以我们能确定 LCA，直接返回 \(fid(2)\)，也就是 \(4\)

然后来到 \(3\)，将 \(vis[3]=1\)，没有子节点，发现有询问 \((3,2)(3,5)\)，这时候 \(vis[2]=1,vis[5]=0\)，所以能确定第一个询问的 LCA，记录 LCA\((3,2)=fid(2)=4\)

然后来到 \(5\)，将 \(vis[5]=1\)，发现有询问 \((3,5)(4,5)\)，我们发现两个都可以确定，记录 LCA\((3,5)=fid(3)=1\)， LCA\((4,5)=fid(4)=4\)

至此算法结束。

有的人可能会问，要是出现下面的情况怎么办？

要是查 \((1,2)\) 的话，不就会返回 \(fid(2)\) 递归下去不就是 \(6\) 了吗？

注意我们是在子树全遍历完才会修改当前点的 \(f\) 的值，所以不会出现这个情况

code：

#include#define INF 0x3f3f3f3f#define N 2000100using namespace std;int n,m,s,fa[N],vis[N],head[N],cnt,Head[N],cnt1=1;struct sb{int u,v,next,lca;}e[N],e1[N];inline void add(int u,int v){e[++cnt].v=v;e[cnt].next=head[u];head[u]=cnt;}inline void Add(int u,int v){e1[++cnt1].v=v;e1[cnt1].next=Head[u];Head[u]=cnt1;}inline int fid(int x){if(fa[x]==x)return x;return fa[x]=fid(fa[x]);}inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!="-";ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}inline void DFS(int x,int f){    vis[x]=1;    for(int i=head[x];i;i=e[i].next)    {        int v=e[i].v;        if(v==f)continue;        if(!vis[v])DFS(v,x),fa[v]=x;    }    for(int i=Head[x];i;i=e1[i].next)    {        int v=e1[i].v;        if(vis[v])e1[i].lca=e1[i^1].lca=fid(v);    }}signed main(){    n=read(),m=read(),s=read();    for(int i=1;i<=n;i++)fa[i]=i;    for(int i=1;i<=n-1;i++)    {        int u=read(),v=read();        add(u,v);        add(v,u);    }    for(int i=1;i<=m;i++)    {        int u=read(),v=read();        Add(u,v);        Add(v,u);    }    DFS(s,0);    for(int i=2;i<=cnt1;i+=2)        cout<

#include #define N 1000100#define endl "\n"using namespace std;struct sb{int u,v,next;}e[N];int dep[N],fa[N],siz[N],head[N],son[N],rt,n,m,cnt,top[N];inline void add(int u,int v){e[++cnt].u=u;e[cnt].v=v;e[cnt].next=head[u];head[u]=cnt;}inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!="-";ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}inline void dfs1(int x,int deep,int f){    dep[x]=deep;fa[x]=f;siz[x]=1;    int maxn=-1;    for(int i=head[x];i;i=e[i].next)    {        if(e[i].v!=f)        {            dfs1(e[i].v,deep+1,x);            siz[x]+=siz[e[i].v];            if(siz[e[i].v]>maxn)maxn=siz[e[i].v],son[x]=e[i].v;        }    }    return ;}inline void dfs2(int x,int tp){    top[x]=tp;    if(!son[x])return ;    dfs2(son[x],tp);    for(int i=head[x];i;i=e[i].next)        if(e[i].v!=fa[x]&&e[i].v!=son[x])dfs2(e[i].v,e[i].v);    return ;}inline int LCA(int x,int y){    while(top[x]!=top[y])    {        if(dep[top[x]]>=dep[top[y]])x=fa[top[x]];        else y=fa[top[y]];    }    return dep[x]