学步园

题目 ： http://poj.org/problem?id=1986

求最近公共祖先的tarjan 算法。

离线算法、时间复杂度为O(n)

基本框架 ：

• 先用随便一种数据结构(链表就行),把关于某个点的所有询问标在节点上,保证遍历到一个点,能得到所有有关这个节点LCA 查询
• 建立并查集.注意:这个并查集只可以把叶子节点并到根节点,即getf(x)得到的总是x的祖先
• 深度优先遍历整棵树,用一个Visited数组标记遍历过的节点,每遍历到一个节点将Visite[i]设成True 处理关于这个节点(不妨设为A)的询问,若另一节点(设为B)的Visited[B]==True,则回应这个询问,这个询问的结果就是getf(B).
  否则什么都不做
• 当A所有子树都已经遍历过之后,将这个节点用并查集并到他的父节点(其实这一步应该说当叶子节点回溯回来之后将叶子节点并到自己,并DFS另一子树)
• 当一颗子树遍历完时,这棵子树的内部查询(即LCA在这棵子树内部)都已经处理了

#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
#define PII pair<int, int>
const int maxn = 100005;
vector<PII> G[maxn];
struct Edge{
    int v, c, next;
}edge[maxn<<1];
int E, head[maxn], n, m;
int out[maxn], dep[maxn], p[maxn];
bool vis[maxn];
int Find(int x){return x == p[x] ? x : p[x] = Find(p[x]);}
void init(){
    E = 0;
    memset(head, -1, sizeof(head));
    memset(vis, false, sizeof(vis));
    memset(dep, 0, sizeof(dep));
    for (int i = 1; i <= n; i++)p[i] = i;
}
void add_edge(int u, int v, int c){
    edge[E].v = v;
    edge[E].c = c;
    edge[E].next = head[u];
    head[u] = E++;
}
void LCA(int fa, int u, int d){
    dep[u] = d;
    for (int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].v, c = edge[i].c;
        if (v == fa)continue;
        LCA(u, v, d + c);
        p[v] = u;
    }
    vis[u] = true;
    for (int i = 0; i < G[u].size(); i++){
        int v = G[u][i].first, e = G[u][i].second;
        if (vis[v]){
            out[e] = dep[u] + dep[v] - 2 * dep[Find(v)];
        }
    }
    return ;
}

int main(){
    scanf("%d%d", &n, &m);
    init();
    for (int i = 1; i <= m; i++){
        int a, b, c;
        char str[2];
        scanf("%d%d%d%s", &a, &b, &c, str);
        add_edge(a, b, c);
        add_edge(b, a, c);
    }
    int k;
    scanf("%d", &k);
    for (int i = 1; i <= k; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        G[a].push_back(make_pair(b, i));
        G[b].push_back(make_pair(a, i));
    }
    LCA(-1, 1, 0);
    for (int i = 1; i <= k; i++)printf("%d\n", out[i]);
    return 0;
}