lca.cpp

/// Topic: LCA, O(sqrt(height)).
#include<bits/stdc++.h>
using namespace std;
#define nx 1001

int depth[nx];
int parent[nx];
int block_sz;
int jump_parent[nx];

vector<int> graph[nx];

void addEdge(int u, int v)
{
    graph[u].push_back(v);
    graph[v].push_back(u);
}

void dfs(int cur, int prev)
{
    parent[cur] = prev;

    depth[cur] = depth[prev] + 1;
    for(auto x: graph[cur])
    {
        if(x != prev) dfs(x, cur);
    }
}

int LCANaive(int u, int v)
{
    if(u == v) return u;
    if(depth[u] > depth[v]) swap(u,v);
    v = parent[v];
    return LCANaive(u,v);
}

void preprocess()
{
    depth[0] = -1;
    dfs(1,0);
}

void dfsSQRT(int cur, int prev)
{
    depth[cur] = depth[prev] + 1;
    parent[cur] = prev;

    if(depth[cur] % block_sz == 0) jump_parent[cur] = parent[cur];
    else jump_parent[cur] = jump_parent[prev];

    for(auto x: graph[cur])
    {
        if(x != prev) dfs(x, cur);
    }
}

int LCASQRT(int u, int v)
{
    while(jump_parent[u] != jump_parent[v])
    {
        if(depth[u] > depth[v]) swap(u,v);

        v = jump_parent[v];
    }

    /// u and v have same jump_parent
    return LCANaive(u,v);
}
int main()
{
    freopen("in.txt", "r", stdin);a
    int n;
    cin >> n;
    for(int i = 0; i <n; i++)
    {
        int u,v;
        cin >> u >> v;
        //cout << u << " " << v << endl;
        addEdge(u,v);
    }

    preprocess();
    cout << LCANaive(11,8)<<endl;
    cout << LCANaive(3,13)<<endl;
    cout << LCASQRT(11,8)<<endl;
    cout << LCASQRT(3,13)<<endl;
    return 0;
}
/*
12
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
9 10
9 11
7 12
7 13

*/