LCA

求LCA（最近公共祖先）的算法有好多，按在线和离线分为在线算法和离线算法。

离线算法有基于搜索的Tarjan算法较优，而在线算法则是基于dp的ST算法较优。

本文讲述ST算法。

这个算法是基于RMQ（区间最大最小值编号）的，而求LCA就是把树通过深搜得到一个序列，然后转化为求区间的最小编号。

比如说给出这样一棵树。

我们通过深搜可以得到这样一个序列：

节点ver 1 3 1 2 5 7 5 6 5 2 4 2 1 (先右后左)
深度deep 1 2 1 2 3 4 3 4 3 2 3 2 1 
首位first 1 4 2 11 5 8 6 

搜索得到序列之后假如我们想求4 和 7的 LCA

那么我们找4和7在序列中的位置通过first 数组查找发现在6---11

即7 5 6 5 2 4 在上面图上找发现正好是以2为根的子树。而我们只要找到其中一个深度最小的编号就可以了、

这时候我们就用到了RMQ算法。

维护一个dp数组保存其区间深度最小的下标，查找的时候返回就可以了。

比如上面我们找到深度最小的为2点，返回其编号10即可。

这部分不会的可以根据上面链接研究一些RMQ

//ver:节点编号 deep：深度 first：点编号位置 dir：距离
int sz, ver[2 * MX], deep[2 * MX], first[MX], dp[2 * MX][30], vis[MX], dir[MX];
void init(int n) {
    for (int i = 0; i <= n; i++) dir[i]=vis[i] = 0;
    sz = 0;
}
void dfs(int u , int dep) {
    vis[u] = true; ver[++sz] = u;
    first[u] = sz; deep[sz] = dep;
    for (int i = head[u]; ~i ; i = E[i].nxt) {
        if ( vis[E[i].v] ) continue;
        int v = E[i].v;
        dir[v] = dir[u] + E[i].w;
        dfs(v, dep + 1);
        ver[++sz] = u; deep[sz] = dep;
    }
}
void ST(int n) {
    for (int i = 1; i <= n; i++) dp[i][0] = i;
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            int a = dp[i][j - 1] , b = dp[i + (1 << (j - 1))][j - 1];
            dp[i][j] = deep[a] < deep[b] ? a : b;
        }
    }
}
//中间部分是交叉的。
int RMQ(int l, int r) {
    int k = 0;
    while ((1 << (k + 1)) <= r - l + 1) k++;
    int a = dp[l][k], b = dp[r - (1 << k) + 1][k]; //保存的是编号
    return deep[a] < deep[b] ? a : b;
}
int LCA(int u , int v) {
    int x = first[u] , y = first[v];
    if (x > y) swap(x, y);
    int ret = RMQ(x, y);
    return ver[ret];
}
void pre_solve(int n) {
    dir[1] = 1;
    dfs(1, 1);
    ST(sz);
}