倍增\ tarjan求lca

对于每个节点v，记录anc[v][k]，表示从它向上走2步后到达的节点（如果越过了根节点，那么anc[v][k]就是根节点）。

dfs函数对树进行的dfs，先求出anc[v][0]，再利用anc[v][k] = anc[anc[v][k - 1]][k - 1]  （从v向上2步即为从v向上2步再向上2步）

求出其他anc[v][k]的值

lca(u, v)函数寻找u和v的lca， 首先把u和v调整到一个高度。如果此时u和v重合，那么这就是我们要找的lca，如果他们补充和，就不断的寻找一个最小的k，使得

anc[u][k] = anc[v][k]

int anc[maxn][], deep[maxn];

int dfs(int u, int fa)

{

    for(int i = ; i < ; i++)

        anc[u][i] = anc[anc[u][i - ]][i - ];

    for(int i = head2[u]; i != -; i = Edge[i].next)

    {

        int v = Edge[i].v;

        if(v == fa || deep[v]) continue;

        anc[v][] = u;

        deep[v] = deep[u] + ;

        dfs(v, u);

    }

}

int lca(int u, int v)

{

    if(deep[u] < deep[v]) swap(u, v);

    for(int i =  - ; i >= ; i--)

        if(deep[anc[u][i]] >= deep[v])

            u = anc[u][i];

    for(int i =  - ; i >= ; i--)

    {

        if(anc[u][i] != anc[v][i])

        {

            u = anc[u][i];

            v = anc[v][i];

        }

    }

    if(u == v) return u;

    return anc[u][];

}

tarjan求lca

1.任选一个点为根节点，从根节点开始。

2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。

3.若是v还有子节点，返回2，否则下一步。

4.合并v到u上。

5.寻找与当前点u有询问关系的点v。

合并就用并查集就好了

板子先欠着

　　　　　　6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。