题目描述

原题地址：洛谷

由于某些原因，我不想在COGS上刷题了，于是转战洛谷。

用此题练习一下倍增LCA。

题解

用$anc(i,j)$表示$i$的第$2^j$个祖先。

那么显然$anc(i,j)=anc(anc(i,j-1),j-1)$，这句话的意思是$i$的第$2^j$个祖先是$i$的第$2^{j-1}$个祖先的第$2^{j-1}$个祖先。

对于两个树上的点，要求他们的LCA，首先考虑一种暴力的算法：

暴力法

• 先将两个点的深度统一。
• 一步一步地向上跳，直到两个点在同一个位置，这个位置就是他们的LCA。

先进的方法

同样是分成两步

统一两个点的深度

使用类似快速幂的二进制拆分思想，可以在$O(\log n)$的时间内完成。

向上跳

可以考虑到，如果我们跳多了，会出现问题，所以我们尽量少的跳，每次除以二。

最后两个点的位置一定在LCA处或者在LCA的下一层。

此题有点卡常。。需要加一些快读快写之类的魔法

代码

#include<bits/stdc++.h>
using namespace std;
inline char getc() { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline int gn() { 
    register int k = 0, f = 1;
    register char c = getc();
    for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}
const int maxn = 500010;
vector<int> g[maxn];
void addedge(int f, int t)
{ 
    g[f].push_back(t);
    g[t].push_back(f);
}
int n, m, s;
int dep[maxn], anc[maxn][20];
void dfs(int fa, int no)
{ 
    anc[no][0] = fa;
    dep[no] = dep[fa] + 1;
    for (int i = 1; i < 20; ++i) anc[no][i] = anc[anc[no][i - 1]][i - 1];
    for (int i = 0; i < g[no].size(); ++i)
        if (g[no][i] == fa) continue;
        else dfs(no, g[no][i]);
}
int lca(int u, int v)
{ 
    dep[u] < dep[v] ? swap(u, v), 0 : 0;
    for (int d = dep[u] - dep[v], k = 0; d; d >>= 1, ++k) u = (d & 1) ? anc[u][k] : u;
    for (int k = 19; k >= 0; --k) anc[u][k] != anc[v][k] ? u = anc[u][k], v = anc[v][k] : 0;
    return u == v ? u : anc[u][0];
}
int main()
{ 
    n = gn(), m = gn(), s = gn();
    for (register int i = 1; i < n; ++i)
    { 
        register int x, y;
        x = gn(), y = gn();
        addedge(x, y);
    }
    dfs(s, s);
    for (register int i = 1; i <= m; ++i)
    { 
        register int u, v;
        u = gn(), v = gn();
        puts(to_string(lca(u, v)).c_str());
    }
}