总结下求 LCA 的方法：

Tarjan

　　这是种离线算法，要把所有的查询读入，然后去求答案．

vector<pair<int, int> > que[N];
vector<int> G[N];
void add_edge(int u, int v)
{
    G[u].push_back(v);
}
void init()
{
    for (int i = 1; i < N; i++) {
        G[i].clear();
        f[i] = i;
        que[i].clear();
    }
}
void dfs(int x)
{
    vis[x] = 1;
    for (auto v: G[x]) {
        if (vis[v])
            continue;
        dfs(v);
        f[v] = x;
    }
    for (auto v: que[x]) {
        if (vis[v.first]) {
            ans[v.second] = root(v.first);
        }
    }
}

当查询量过大时不合适用这种方法．

比如，这道题：　http://www.lydsy.com/JudgeOnline/problem.php?id=1832

要查询的量为 50 万，150万次的lca查询，内存会爆．

倍增法

　　用 f[v][j] 来表示顶点 v 的 2^j 的祖先，就有 f[v][0] 是 v 的父亲．

  void dfs(int x)
{
    for (auto v : G[x]) {
        if (f[x][0] == v)
            continue;
        f[v][0] = x;
        dep[v] = dep[x] + 1;
        dfs(v);
    }
}

RMQ

树链剖分

　　将树分成一条一条的链后，不同链时就往链上靠，在同一条链时，链上的顶点就是 LCA 了．

int lca(int x, int y)
{
    while (top[x] ^ top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        x = f[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}