POJ1330Nearest Common Ancestors

时间：2025-04-12 23:05:13

去博客园看该题解

题意

第一行输入T，有T组数据。
对于每组数据，给出一棵树，先输入n，然后n-1行，每行两个数a，b，表示a是b的父亲；第n行输入两个数A,B表示询问A和B的最近公共祖先。

题解

LCA模板题。

参见LCA学习笔记

LCA倍增算法&POJ1330标程

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

const int N=+;

vector <int> son[N];

int T,n,depth[N],fa[N][],in[N],a,b;

void dfs(int prev,int rt){

    depth[rt]=depth[prev]+;

    fa[rt][]=prev;

    for (int i=;(<<i)<=depth[rt];i++)

        fa[rt][i]=fa[fa[rt][i-]][i-];

    for (int i=;i<son[rt].size();i++)

        dfs(rt,son[rt][i]);

}

int LCA(int a,int b){

    if (depth[a]>depth[b])

        swap(a,b);

    for (int i=depth[b]-depth[a],j=;i>;i>>=,j++)

        if (i&)

            b=fa[b][j];

    if (a==b)

        return a;

    int k;

    for (k=;(<<k)<=depth[a];k++);

    for (;k>=;k--)

        if ((<<k)<=depth[a]&&fa[a][k]!=fa[b][k])

            a=fa[a][k],b=fa[b][k];

    return fa[a][];

}

int main(){

    scanf("%d",&T);

    while (T--){

        scanf("%d",&n);

        for (int i=;i<=n;i++)

            son[i].clear();

        memset(in,,sizeof in);

        for (int i=;i<n;i++){

            scanf("%d%d",&a,&b);

            son[a].push_back(b);

            in[b]++;

        }

        depth[]=-;

        int rt=;

        for (int i=;i<=n&&rt==;i++)

            if (in[i]==)

                rt=i;

        dfs(,rt);

        scanf("%d%d",&a,&b);

        printf("%d\n",LCA(a,b));

    }

    return ;

}

相关文章