POJ 1330 Tarjan LCA、ST表（其实可以数组模拟）

题意：给你一棵树，求两个点的最近公共祖先。

思路：因为只有一组询问，直接数组模拟好了。

（写得比较乱）

原题请戳这里

#include <cstdio>

#include <bitset>

#include <cstring>

#include <algorithm>

using namespace std;

int first[10005],v[10005],next[10005];

int main()

{

    int cas;

    scanf("%d",&cas);

    while(cas--)

    {

        bitset<10005> b;

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

        int tot=1,n,x,s,e;

        scanf("%d",&n);

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

        {

            scanf("%d%d",&v[tot],&x);

            next[i]=first[x];

            first[x]=tot++;

        }

        scanf("%d%d",&s,&e);

        b.flip(s);

        while(first[s]!=-1)

        {

            s=v[first[s]];

            b.flip(s);

        }

        if(b.test(e))

        {

            printf("%d\n",e);

            goto end;

        }

        while(first[e]!=-1)

        {

            e=v[first[e]];

            if(b.test(e))

            {

                printf("%d\n",e);

                break;

            }

        }

        end:;

    }

} 

搞个Tarjan玩玩

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int first[10005],cas,next[10005],v[10005],s,e,ans,f[10005];

bool vis[10005];

int find(int x)

{

    return f[x]==x?x:f[x]=find(f[x]);

}

void Tarjan(int x)

{

    f[x]=x;

    for(int i=first[x];~i;i=next[i])

    {

        Tarjan(v[i]);

        f[find(v[i])]=x;

    }

    vis[x]=1;

    if(x==s&&vis[e])

    {

         ans=find(e);

    }

    else if(x==e&&vis[s])

    {

        ans=find(s);

    }

}

int main()

{

    scanf("%d",&cas);

    while(cas--)

    {

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

        memset(vis,0,sizeof(vis));

        int tot=1,n,x,root;

        scanf("%d",&n);

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

        {

            scanf("%d%d",&x,&v[tot]);

            next[i]=first[x];

            vis[v[tot]]=1;

            first[x]=tot++;

        }

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

        {

            if(!vis[i])

            {

                root=i;

                break;

            }

        }

        memset(vis,0,sizeof(vis));

        scanf("%d%d",&s,&e);

        Tarjan(root);

        printf("%d\n",ans);

    }

} 

（对于这道题，还是模拟大法好啊）

如果给多组询问，就只能用Tarjan或者ST了。。

ST的：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int cases,root,n,jyx,jyy,tot,fa[100005][19];

int in[100005],dep[100005],first[100005],next[100005],v[100005];

void add(int x,int y){

    v[tot]=y;

    next[tot]=first[x];

    first[x]=tot++;

}

void dfs(int x)

{

    for(int i=1;i<=18;i++)

    {

        fa[x][i]=fa[fa[x][i-1]][i-1];

    }

    for(int i=first[x];~i;i=next[i])

    {

        dep[v[i]]=dep[x]+1;

        dfs(v[i]);

    }

}

int lca(int x,int y)

{

    if(dep[x]<dep[y])swap(x,y);

    for(int i=18;i>=0;i--)

    {

        if(dep[x]>=dep[y]+(1<<i))x=fa[x][i];

        if(x==y)return x;

    }

    for(int i=18;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

    }

    return fa[x][0];

}

int main()

{

    scanf("%d",&cases);

    while(cases--){

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

        memset(in,0,sizeof(in));

        tot=0;

        scanf("%d",&n);

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

            scanf("%d%d",&jyx,&jyy);

            fa[jyy][0]=jyx;

            add(jyx,jyy);

            in[jyy]++;

        }

        scanf("%d%d",&jyx,&jyy);

        for(int i=1;i<=n;i++)if(!in[i])root=i;

        dfs(root);

        printf("%d\n",lca(jyx,jyy));

    }

}