Distance Queries

LCA問題：

LCA：Least Common Ancestors（最近公共祖先），對於一棵有根樹T的任意兩個節點u，v，求出LCA(T, u, v)，即離跟最遠的節點x，使得x同時是u和v的祖先。
在線算法：用比較長的時間做預處理，但是等信息充足以後每次回答詢問只需要用比較少的時間。
離線算法：先把所有的詢問讀入，然後一起把所有詢問回答完成。 下面這個博客有LCA問題的介紹，以及Tarjin 和 RMQ 算法的介紹。 http://www.cppblog.com/Icyflame/archive/2009/07/04/88987.html

Tarjin （離線算法）

Tarjin算法是離線算法，先獲得所有詢問，然後統一處理，利用DFS + 並查集實現。 Tarjan算法處理某一個節點X的過程分為這麼幾步：
1、建立只有一個X節點的集合。也就是在並查集裡，root[X] = X，並且標記該節點已經訪問。
2、處理所有關於X的詢問，對於(X, Y)，如果Y已經處理過，那麼LCA(X, Y) = find(Y)，也就是Y在並查集裡的根節點。如果Y沒有處理過，忽略這個詢問。
要處理所有詢問，必須將（X，Y）這個詢問分別加到X和Y結點上。 3、遞歸這個過程處理X的孩子。
4、將root[X]設為father[X]，也就是X的父親。
偽代碼：

//parent為並查集，FIND為並查集的查找操作
 2 Tarjan(u)
 3     visit[u] = true
 4     for each (u, v) in QUERY
 5         if visit[v]
 6             ans(u, v) = FIND(v)
 7     for each (u, v) in TREE    
 8         if !visit[v]
 9             Tarjan(v)
10             parent[v] = u

下面的博客關於Tarjin算法解釋的比較清楚。 http://hi.baidu.com/billdu/item/9938ed34ab9416352e20c41f

DFS + RMQ （在線算法）

LCA算法可以轉化為RMQ算法： （1）DFS：從樹T的根開始，進行深度優先遍歷，並記錄下每次到達的頂點。第一個的結點是root(T)，每經過一條邊都記錄它的端點。由於每條邊恰好經過2次，因此一共記錄了2n-1個結點，用E[1, ... , 2n-1]來表示。 在DFS的過程中，同時記錄下每個頂點的深度。用depth[]記錄。 在DFS的過程中，記錄下第一次到達該頂點的數組下標。
（2）計算R：用R[i]表示E數組中第一個值為i的元素下標，即如果R[u] < R[v]時，DFS訪問的順序是E[R[u], R[u]+1, ..., R[v]]。雖然其中包含u的後代，但深度最小的還是u與v的公共祖先。
（3）RMQ：當R[u] ≥ R[v]時，LCA[T, u, v] = RMQ(L, R[v], R[u])；否則LCA[T, u, v] = RMQ(L, R[u], R[v])，計算RMQ。
由於RMQ中使用的ST算法是在線算法，所以這個算法也是在線算法。
http://www.cnblogs.com/scau20110726/archive/2013/05/26/3100812.html
http://dongxicheng.org/structure/lca-rmq/

題目大意：

求一棵樹上兩個節點（u，v）之間的最短距離，用LCA取出最近公共祖先root。則最短距離為 dis[u] + dis[v] - 2 * dis[root]。其中dis為每個節點到根節點的距離。

Tarjin 算法：

/*   Tarjin 離線算法
struct node
{
    int x, d;
};
int n, m, dis[maxn], ans[maxn], vis[maxn] = {0}, f[maxn];
vector V[maxn], query[maxn];
void init()
{
    scanf("%d%d", &n, &m);
    int a, b;
    char ch;
    node tmp;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d %c", &a, &b, &tmp.d, &ch);
        tmp.x = b;
        V[a].push_back(tmp);
        tmp.x = a;
        V[b].push_back(tmp);
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &a, &b);
        tmp.d = i, tmp.x = b;
        query[a].push_back(tmp);
        tmp.x = a;
        query[b].push_back(tmp);
    }
}
int find(int x)
{
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}
void dfs(int u, int d)
{
    vis[u] = 1, f[u] = u, dis[u] = d;
    for (int i = 0; i < query[u].size(); i++) if (vis[query[u][i].x])
    {
        int v = query[u][i].x, w = query[u][i].d;
        ans[w] = dis[u] + dis[v] - 2 * dis[find(v)];
    }
    for (int i = 0; i < V[u].size(); i++) if (!vis[V[u][i].x])
    {
        int v = V[u][i].x, w = V[u][i].d;
        dfs(v, d + w);
        f[v] = u;
    }

}
int main ()
{
    init();
    dfs(1, 0);
    for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
    return 0;
}
*/

DFS + RMQ 算法：

//DFS + RMQ 在線算法
struct node
{
    int x, d;
};
vector V[maxn];
int E[maxn * 2], D[maxn * 2], first[maxn], vis[maxn], dis[maxn], n, m, top = 1;
int dp[30][maxn * 2];
void init()
{
    scanf("%d%d", &n, &m);
    int a, b;
    char ch;
    node tmp;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d %c", &a, &b, &tmp.d, &ch);
        tmp.x = b;
        V[a].push_back(tmp);
        tmp.x = a;
        V[b].push_back(tmp);
    }
}
void dfs(int u, int dep, int w)
{
    vis[u] = 1, E[top] = u, D[top] = dep, first[u] = top++, dis[u] = w;
    for (int i = 0; i < V[u].size(); i++) if (!vis[V[u][i].x])
    {
        int v = V[u][i].x, cost = V[u][i].d;
        dfs(v, dep + 1, w + cost);
        E[top] = u, D[top++] = dep;
    }
}
void ST(int num)
{
    for (int i = 1; i <= num; i++) dp[0][i] = i;
    for (int i = 1; i <= log2(num); i++)
        for (int j = 1; j <= num; j++) if (j + (1 << i) - 1 <= num)
        {
            int a = dp[i - 1][j], b = dp[i - 1][j + (1 << i >> 1)];
            if (D[a] < D[b]) dp[i][j] = a;
            else dp[i][j] = b;
        }
}
int RMQ(int x, int y)
{
    int k = (int) log2(y - x + 1.0);
    int a = dp[k][x], b = dp[k][y - (1 << k) + 1];
    if (D[a] < D[b]) return a;
    return b;
}
int main ()
{
    init();
    dfs(1, 0, 0);
    ST(top - 1);
    scanf("%d", &m);
    int x, y;
    while(m--)
    {
        scanf("%d%d", &x, &y);
        int a = first[x], b = first[y];
        if (a > b) swap(a, b);
        int pos = RMQ(a, b);
        printf("%d\n", dis[x] + dis[y] - 2 * dis[E[pos]]);
    }
    return 0;
}