LCA
===
###### tags: `Algorithm`

## 提示

* DFS : 建表 $2^n$ 輩祖先, 紀錄時間戳(用來判祖先)

    void DFS( int u, int p, int d)
    {
        tin[u] = t++;

        anc[u][0] = p; used[u][0] = time;
        for( int i=1; 1<<i < d; i++)
        {
            anc[u][i] = anc[ anc[u][i-1] ][i-1];
            //used[u][i] = time;
        }

        for( vector<int>::iterator v=adj[u].begin(); v!=adj[u].end(); v++)
        {
            DFS( *v, u, d+1);
        }

        tout[u] = t++;
    }

* 判祖先

    inline bool isAnc( int a, int b)
    {
        if (a<=0) return 1; // 祖先不存在(爬過頭)
        return  tin[a] < tin[b] && tout[b] < tout[a];
    }

* 由一點 a 往上爬
如果成功(要爬的點是b的祖先)就改爬一半試看看
如果失敗(要爬的點不是b的祖先), 就可以爬過去
目標是爬到成功的前一個, 則 LCA 是他的父親

int LCA( int a, int b)
{
    if (a==b || isAnc(a,b)) return a; 
    if (isAnc(b,a)) return b;

    for( int i=logN; i>=0; i--)
    {
        if (!(isAnc(anc[a][i],b)) //|| used[a][i]<time))
        {
            a = anc[a][i];
        }
    }
    return anc[a][0];
}

:::danger
一般倍增法的步數是大於0
但 lca 是步數大於等於 0
因爲就算是 0 實際上步數是 1
:::

## POJ1330

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
#define maxN 10010
#define logN 15

int N;
int anc[maxN][logN+10], used[maxN][logN+10], time;
vector<int> adj[maxN];
int tin[maxN], tout[maxN], t;

void DFS( int u, int p, int d)
{
    tin[u] = t++;

    anc[u][0] = p; used[u][0] = time;
    for( int i=1; 1<<i < d; i++)
    {
        anc[u][i] = anc[ anc[u][i-1] ][i-1];
        used[u][i] = time;
    }

    for( vector<int>::iterator v=adj[u].begin(); v!=adj[u].end(); v++)
    {
        DFS( *v, u, d+1);
    }

    tout[u] = t++;
}

inline bool isAnc( int a, int b)
{
    if (a<=0) return 1;
    return  tin[a] < tin[b] && tout[b] < tout[a];
}

int LCA( int a, int b)
{
    if (a==b || isAnc(a,b)) return a; 
    if (isAnc(b,a)) return b;

    for( int i=logN; i>=0; i--)
    {
        if (!(isAnc(anc[a][i],b) || used[a][i]<time))
        {
            a = anc[a][i];
        }
    }
    return anc[a][0];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    for( time=1; time<=T; time++)
    {
        t=0;
        for( int i=0; i<maxN; i++)
        {
            adj[i].clear();
            adj[i].reserve(100);
        }

        cin >> N;
        long long rt = ((1+N)*N)>>1;
        for( int i=0; i<N-1; i++)
        {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            rt-=b;
        }
        DFS( rt, -1, 0);

        int a, b;
        cin >> a >> b;
        cout << LCA(a,b) << '\n';
     }
}