Closest Common Ancestors---poj1470（LCA+离线算法）

题意是给出一颗树，q个查询，每个查询都是求出u和v的LCA；

以下是寻找LCA的预处理过程：

void LCA(u)
{
    for(u的每个儿子v)
　　{
        LCA(v);
        union(u,v);//并到一个集合中去
    }
    visit[u]=1;
    for(查询中u的每个儿子v)
　　{
        if(visit[v])
            u,v的最近公共祖先是father[getfather(v)];
    }
}

详细解释

图文详解

本题可以使用预处理的方式，也可以使用离线处理，由于不需要求任意两数之间的LCA所以可以使用离线算法；

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <math.h>

using namespace std;

#define met(a, b) memset(a, b, sizeof(a))
#define N 953
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;

typedef long long LL;

vector<int>G[N];
vector<int>Q[N];

int f[N], ans[N], vis[N];

int Find(int x)
{
    if(x!=f[x])
        return f[x] = Find(f[x]);
    return x;
}

void Union(int x, int y)
{
    int px = Find(x);
    int py = Find(y);

        f[py] = px;
}

void LCA(int u)
{
    for(int i=0, len=G[u].size(); i<len; i++)
    {
        int v = G[u][i];
        LCA(v);
        Union(u, v);
    }
    vis[u] = 1;
    for(int i=0, len=Q[u].size(); i<len; i++)
    {
        int v = Q[u][i];
        if(vis[v])
            ans[f[Find(v)]]++;
    }
}

int main()
{
    int n, root;
    while(scanf("%d", &n) != EOF)
    {
        for(int i=0; i<N; i++)
        {
            G[i].clear();
            Q[i].clear();
        }
        met(vis, 0);

        for(int i=1; i<=n; i++)
        {
            f[i] = i;
            int u, v, cnt;
            scanf("%d:(%d)", &u, &cnt);
            for(int j=1; j<=cnt; j++)
            {
                scanf("%d", &v);
                G[u].push_back(v);
                vis[v] = 1;
            }
        }

        for(int i=1; i<=n; i++)
        if(!vis[i])
        {
            root = i;
            break;
        }

        int q, u, v;

        scanf("%d", &q);

        for(int i=1; i<=q; i++)
        {
            scanf(" (%d%d)", &u, &v);
            Q[u].push_back(v);
            Q[v].push_back(u);
        }

        met(vis, 0);
        met(ans, 0);

        LCA(root);

        for(int i=1; i<=n; i++)
            if(ans[i])
                printf("%d:%d
", i, ans[i]);
    }
    return 0;
}

View Code