倍增&LCA

Skyzhou666 · 2022-10-27 13:44:37 · 算法·理论

快比赛了赶紧学倍增（

P3379 倍增LCA板子题

得开快读才能过（

#include <iostream>
#include <vector>
#define MAXN 500001
using namespace std;

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

int n, m, s, lg[MAXN], dep[MAXN], fa[MAXN][64];
vector <int> g[MAXN];

void dfs(int u, int f)
{
    fa[u][0] = f;
    dep[u] = dep[f] + 1;
    for(int x = 1; x <= lg[dep[u]]; x++)
        fa[u][x] = fa[fa[u][x-1]][x-1];
    for(int x = 0; x < g[u].size(); x++)
        if(g[u][x] != f) dfs(g[u][x], u);
}

int lca(int a, int b)
{
    if(dep[a] < dep[b]) swap(a, b);
    while(dep[a] > dep[b]) a = fa[a][lg[dep[a]-dep[b]]-1];
    if(a == b) return a;
    for(int x = lg[dep[a]]-1; x >= 0; x--)
        if(fa[a][x] != fa[b][x]) a = fa[a][x], b = fa[b][x];
    return fa[a][0];
}

int main()
{
    int u, v;
    n = read(); m = read(); s = read();
    for(int x = 0; x < n-1; x++)
    {
        u = read(); v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int x = 1; x <= n; x++) lg[x] = lg[x-1] + (1 << lg[x-1] == x);
    dfs(s, 0);
    for(int x = 0; x < m; x++)
    {
        u = read(); v = read();
        cout << lca(u, v) << endl;
    }
    return 0;
}