HDU 1330 Nearest Common Ancestors(求两个点的近期公共祖先)

题目链接：

在线算法：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 40010;

struct nod{

    int to,next,w;

}edge[maxn*2];

int head[maxn],ip,tot;

bool vis[maxn];

int R[maxn*2],ver[maxn*2];

int dp[maxn*2][25];

int first[maxn];

int dis[maxn];

bool isroot[maxn];

void init(){

    memset(head,-1,sizeof(head));

    memset(isroot,0,sizeof(isroot));

    memset(vis,false,sizeof(vis));

    dis[1]=0,ip=0,tot=0;

}

void add(int u,int v){

    edge[ip].to=v;

    edge[ip].next=head[u];

    head[u]=ip++;

}

/***

ver[i]=x:第i个点是x.

first[i]=x: 点i第一次出现的位置是x

R[i]=x：第i个点的深度为x;

dis[i]=x;点i到根节点的距离为x.

***/

void dfs(int u,int dept){

    vis[u]=true,ver[++tot]=u,first[u]=tot,R[tot]=dept;

    for(int i=head[u];i!=-1;i=edge[i].next){

        int v=edge[i].to;

        if(!vis[v]){

            dfs(v,dept+1);

            ver[++tot]=u,R[tot]=dept;

        }

    }

}

void ST(int n){

    for(int i=1;i<=n;i++) dp[i][0]=i;

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

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

            int a = dp[j][i-1],b=dp[j+(1<<(i-1))][i-1];

            if(R[a]<R[b]) dp[j][i]=a;

            else dp[j][i]=b;

        }

    }

}

int RMQ(int l,int r){

    int k=0;

    while(1<<(k+1)<=r-l+1)

        k++;

    int x = dp[l][k], y=dp[r-(1<<k)+1][k];

    if(R[x]<R[y]) return x;

    else return y;

}

int LCA(int u,int v){

    u=first[u],v=first[v];

    if(u>v) swap(u,v);

    return ver[RMQ(u,v)];

}

int main(){

    int t,n,m;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        init();

        for(int i=0;i<n-1;i++){

            int u,v,w;

            scanf("%d%d",&u,&v);

            add(u,v);

            add(v,u);

            isroot[v]=1;

        }

        int x,y;

        scanf("%d%d",&x,&y);

        int root;

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

            if(!isroot[i]){

                root=i;

                break;

            }

        }

        dfs(root,1);

        ST(n*2-1);

        printf("%d\n",LCA(x,y));

    }

    return 0;

}

离线算法：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 40010;

struct nod{

    int u,v,next,w,lca;

}edge[maxn*2],edge1[maxn];

int par[maxn],ancestors[maxn];

int head[maxn];

int dis[maxn],ip;

int x,y;

bool vis[maxn];

bool root[maxn];

void init(){

    memset(head,-1,sizeof(head));

    memset(vis,false,sizeof(vis));

    for(int i=0;i<maxn;i++) root[i]=true;

    for(int i=1;i<maxn;i++) par[i]=i;

    ip=0;

}

int find_par(int x){

    if(x!=par[x]) return par[x]=find_par(par[x]);

    return par[x];

}

void Union(int u,int v){

    u=find_par(u);

    v=find_par(v);

    if(u!=v) par[v]=u;

}

void add(int u,int v){

    edge[ip].v=v;

    edge[ip].next=head[u];

    head[u]=ip++;

}

bool ans;

void tarjan(int u){

    vis[u]=1;

    for(int i=head[u];i!=-1;i=edge[i].next){

        int v = edge[i].v;

        if(!vis[v]){

            dis[v]=dis[u]+edge[i].w;

            tarjan(v);

            Union(u,v);

        }

    }

    if(u==x&&vis[y]&&!ans){

        ans=1;

        printf("%d\n",find_par(y));

        return;

    }

    if(u==y&&vis[x]&&!ans){

        ans=1;

        printf("%d\n",find_par(x));

        return;

    }

}

int main()

{

    int t,n;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        init();

        for(int i=0;i<n-1;i++){

            int u,v;

            scanf("%d%d",&u,&v);

            root[v]=false;

            add(u,v);

            add(v,u);

        }

        ans=0;

        scanf("%d%d",&x,&y);

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

            if(root[i]){

                tarjan(i);

                break;

            }

        }

    }

    return 0;

}