lca.cpp

最近公共祖先(LCA)

#include<vector>
#include<stdio.h>

using namespace std;

int pp;
int result;
int pos[100008];
vector<int> vec[100008];


void DFS(int p) //深度搜索初始化
{
    vector<int>::iterator start,end;
    start = vec[p].begin(); end = vec[p].end();
    for(;start!=end;start++) DFS((*start));
    pos[p] = pp++;
}

void RMQ(int p,int a,int b,int temp) //线段树查询
{
    vector<int>::iterator start,end;
    if(temp < pos[a] && pos[p] > pos[b])
    {
        start = vec[p].begin(); end = vec[p].end();
        for(;start!=end;start++)
        {
            if(pos[(*start)] >= pos[b] && temp < pos[a])
            {
                RMQ((*start),a,b,temp);
                return;
            }
            temp = pos[(*start)];
        }
        result = p;
    }
    else result = p;
}

int main()
{
    int m,n,t,i,j,a,b;
    while(scanf("%d",&m)!=EOF)
    {
        for(i=1;i<=m;i++)
        {
            scanf("%d",&t);
            if(t == 0) j = i;
            vec[t].push_back(i); 
        }
        pp = 0;
        DFS(j);
        scanf("%d",&n);
        while(n--)
        {
            scanf("%d%d",&a,&b);
            if(pos[a] == pos[b]) result = a;
            if(pos[a] < pos[b]) RMQ(j,a,b,-1);
            else RMQ(j,b,a,-1);
            printf("%d\n",result);
        }
        
        while(m--) vec[m+1].clear();
    }
    return 0; 
}