百度百科

Definition&Solution

对于求树上\(u\)和\(v\)两点的LCA，使用在线倍增可以做到\(O(nlogn)\)的复杂度。在NOIP这种毒瘤卡常比赛中，为了代码的效率，常使用tarjan的离线LCA算法预处理各点复杂度。其复杂度为\(O(n~\alpha~(a))\)

在算法中，使用dfs遍历每个点。在回溯时，使用并查集维护每个被遍历到的点的已经回溯的最浅祖先。显然对于两个点，当一个点被后遍历到的时候，他们的LCA就是被先遍历到的点被维护的祖先。

在使用中使用并查集维护各点的祖先关系，使用路径压缩与按秩合并，使得并查集复杂度是\(O(\alpha~(n))\)，一共查询\(O(n)\)次，所以总时间复杂度为\(O(n~\times~\alpha~(n))\)。

Example

【P3379】最近公共祖先

Description

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

Input

第一行包含三个正整数\(N\)、\(M\)、\(S\)，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来\(N-1\)行每行包含两个正整数\(x\)、\(y\)，表示\(x\)结点和\(y\)结点之间有一条直接连接的边

接下来\(M\)行每行包含两个正整数\(a\)、\(b\)，表示询问\(a\)结点和\(b\)结点的最近公共祖先。

Output

输出包含\(M\)行，每行包含一个正整数，依次为每一个询问的结果。

Sample Input

        5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
    

Sample Output

        4
4
1
4
4
    

Solution

板子题要啥solution

Code

        #include<cstdio>
#include<algorithm>
#define rg register
#define ci const int
#define cl const long long int

typedef long long int ll;

namespace IO {
    char buf[90];
}

template<typename T>
inline void qr(T &x) {
    char ch=getchar(),lst=' ';
    while(ch>'9'||ch<'0') lst=ch,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(lst=='-') x=-x;
}

template<typename T>
inline void write(T x,const char aft,const bool pt) {
    if(x<0) x=-x,putchar('-');
    int top=0;
    do {
        IO::buf[++top]=x%10+'0';
        x/=10;
    } while(x);
    while(top) putchar(IO::buf[top--]);
    if(pt) putchar(aft);
}

template<typename T>
inline T mmax(const T a,const T b) {return a>b?a:b;}
template<typename T>
inline T mmin(const T a,const T b) {return a<b?a:b;}
template<typename T>
inline T mabs(const T a) {return a<0?-a:a;}

template<typename T>
inline void mswap(T &a,T &b) {
    T temp=a;a=b;b=temp;
}

const int maxm = 1000010;
const int maxn = 500010;

struct Edge {
    int to,nxt,num,ans;
};
Edge edge[maxm],ask[maxm];int hd[maxn],ha[maxn],ecnt,acnt=1;
inline void cont(ci from,ci to) {
    Edge &e=edge[++ecnt];
    e.to=to;e.nxt=hd[from];hd[from]=ecnt;
}
inline void ada(ci a,ci b) {
    Edge &now=ask[++acnt];
    now.to=b;now.nxt=ha[a];ha[a]=acnt;
}

inline bool cmp(const Edge &_a,const Edge &_b) {
    return _a.num < _b.num;
}

int n,m,s;
int frog[maxn],sz[maxn],as[maxn];
bool vis[maxn];

void dfs(ci,ci);
int find(ci);

int main() {
    qr(n);qr(m);qr(s);
    rg int a,b;
    for(rg int i=1;i<n;++i) {
        a=b=0;qr(a);qr(b);cont(a,b);cont(b,a);
        frog[i]=i;sz[i]=1;as[i]=i;
    }
    frog[n]=n;sz[n]=1;
    for(rg int i=1;i<=m;++i) {
        a=b=0;qr(a);qr(b);
        ada(a,b);ask[acnt].num=i;
        ada(b,a);ask[acnt].num=i;
    }
    dfs(s,0);
    std::sort(ask+1,ask+acnt+1,cmp);
    for(rg int i=2;i<=acnt;i+=2) write(ask[i].ans,'\n',true);
    return 0;
}

void dfs(ci u,ci fa) {
    vis[u]=true;
    for(rg int i=hd[u];i;i=edge[i].nxt) if(edge[i].to != fa) {
        int &to=edge[i].to;
        dfs(to,u);
        int fa=find(u),fb=find(to);
        if(sz[fa] > sz[fb]) {
            sz[fa]+=sz[fb],frog[fb]=fa,as[fa]=u;
        }
        else {
            sz[fb]+=sz[fa],frog[fa]=fb,as[fb]=u;
        }
    }
    for(rg int i=ha[u];i;i=ask[i].nxt) {
        int &v=ask[i].to;
        if(vis[v]) {
            ask[i^1].ans=ask[i].ans=as[find(frog[v])];
        }
    }
}

int find(ci x) {
    return frog[x] == x ? x : frog[x]=find(frog[x]);
}
    

Summary

卡常使我快乐

原文：https://www.cnblogs.com/yifusuyi/p/9716637.html