LCA-Tarjan

Tarjan 求LCA 是一种十分优秀的离线算法（缺点就是必须离线），时间复杂度为 O(n+m)（然而一般的并查集时间复杂度是O(nlogn)），小于树剖、倍增等方法。

其保证时间复杂度的方法是在遍历树的时候记录已经走过的分支口，使得回溯的时候可以O(1)得出两个点的LCA。但是在开始前必须先将要求的点对进行排序，不然算法会退化。

#include <algorithm> //STL通用算法
#include <cmath> //定义数学函数
#include <cstdio> //定义输入/输出函数
#include <iostream> //数据流输入/输出
#include <cstring> //字符串处理
#include <string> //字符串类
#include <ctime> //定义关于时间的函数
#define itn int
#define fro for
#define ll long long
#define reg register
/*#include <bitset> //STL位集容器
#include <cstype> //字符处理
#include <cerrno> //定义错误码
#include <complex> //复数类
#include <clocale> //定义本地化函数
#include <cstdlib> //定义杂项函数及内存分配函数
#include <deque> //STL双端队列容器
#include <exception> //异常处理类
#include <fstream> //文件输入/输出
#include <functional> //STL定义运算函数(代替运算符)
#include <limits> //定义各种数据类型最值常量
#include <list> //STL线性列表容器
#include <map> //STL映射容器
#include <iomanip> //参数化输入/输出
#include <ios> //基本输入/输出支持
#include <iosfwd> //输入/输出系统使用的前置声明
#include <istream> //基本输入流
#include <ostream> //基本输出流
#include <queue> //STL队列容器
#include <set> //STL集合容器
#include <sstream> //基于字符串的流
#include <stack> //STL堆栈容器
#include <stdexcept> //标准异常类
#include <streambuf> //底层输入/输出支持
#include <utility> //STL通用模板类
#include <vector> //STL动态数组容器
#include <cwchar.h>//宽字符处理及输入/输出
#include <cwctype.h> //宽字符分类*/

using namespace std;

int max(int x,int y){
    return x>y?x:y;
}

int min(int x,int y){
    return x<y?x:y;
}

int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

void write(int x){
    int buf[50];
    if (x<0) putchar('-'),x=-x;
    buf[0]=0;
    while (x) buf[++buf[0]]=x%10,x/=10;
    if (!buf[0]) buf[0]=1,buf[1]=0;
    while (buf[0]) putchar('0'+buf[buf[0]--]);
}

int fir[5005000],to[1001000],ne[1001000],firp[5005000],as[1001000],nep[1001000];
int ans[1001000],vis[5005000],f[5001000],fa[5005000]; 
int n,m,s,e,q,a,b;


void add(int u,int v)
{
    to[++e]=v;
    ne[e]=fir[u];
    fir[u]=e;
}

void app(int x,int y)
{
    as[++q]=y;
    nep[q]=firp[x];
    firp[x]=q;
}

int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}

void un(int x,int y)
{
    int xx=find(x);
    int yy=find(y);
    if(xx!=yy) fa[xx]=yy;
}

void tarjan(int x)
{
    for(int i=fir[x];i;i=ne[i])
    {
        int t=to[i];
        if(t==f[x]) continue; 
        f[t]=x;
        tarjan(t);
        un(t,x);
        vis[t]=1;
    }
    for(int i=firp[x];i;i=nep[i])
    {
        int y=as[i];
        if(vis[y]) ans[i]=find(y);
    }
}


int main()
{
    n=read();m=read();s=read();
    for(int i=1;i<=n-1;i++)
        a=read(),b=read(),add(a,b),add(b,a);

    for(int i=1;i<=m;i++)
        a=read(),b=read(),app(a,b),app(b,a);

    for(int i=1;i<=n;i++) fa[i]=i,f[i]=i;

    tarjan(s);

    for(int i=1;i<=m;i++)
        printf("%d\n",max(ans[2*i],ans[2*i-1]));

    return 0;
}