LCA的一些算法

　　LCA，就是求树上任意两点的最近公共祖先

　　（本题图片与代码均为Luogu3379）

　　方法我好像讲过一个，这次把主要的三个一起讲一讲

　　<1> 倍增（O（n log n））

　　我们先考虑最基本的LCA，记录每一个点的父节点和深度。

　　对于两个点x，y，先将它们调到同一高度（令dep[x]>dep[y]，即把x向上移（dep[x]-dep[y])步即可，然后一起往上走就可以了。

　　这复杂度是O（nq）的，所以在此基础上优化。

　　用father[i][j]表示点j向上走2^i步时的点是多少（没有就是-1），然后每次上移只要走log n次即可。

　　预处理的话 father[i][j]]=father[i-1][father[i-1][j]]；递推即可。

　　CODE

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

const int N=,P=;

struct data

{

    int to,next;

}e[N*+];

int head[N*+],dep[N],father[P][N],i,j,n,m,x,y,root,k;

inline void read(int &x)

{

    x=; char ch=getchar();

    while (ch<''||ch>'') ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

}

inline void write(int x)

{

    if (x/) write(x/);

    putchar(x%+'');

}

inline void add(int x,int y)

{

    e[++k].to=y; e[k].next=head[x]; head[x]=k;

}

inline void dfs(int k,int fa,int d)

{

    father[][k]=fa;

    dep[k]=d;

    for (int i=head[k];i!=-;i=e[i].next)

    if (e[i].to!=fa) dfs(e[i].to,k,d+);

}

inline int LCA(int x,int y)

{

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

    for (i=P-;i>=;--i)

    if (((dep[x]-dep[y])>>i)&) x=father[i][x];

    if (x==y) return x;

    for (i=P-;i>=;--i)

    if (father[i][x]!=father[i][y])

    {

        x=father[i][x];

        y=father[i][y];

    }

    return father[][x];

}

int main()

{

    read(n); read(m); read(root);

    memset(e,-,sizeof(e));

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

    memset(father,-,sizeof(father));

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

    {

        read(x); read(y);

        add(x,y); add(y,x);

    }

    dfs(root,-,);

    for (j=;j<P-;++j)

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

    if (father[j][i]==-) father[j+][i]=-; else father[j+][i]=father[j][father[j][i]];

    while (m--)

    {

        read(x); read(y);

        write(LCA(x,y));

        putchar('\n');

    }

    return ;

}

　　<2> DFS序+RMQ（O（n log n））

　　考虑一棵树的DFS序（不懂查百度），如样例的DFS序就是：4 2 4 1 3 1 5 1 4

　　不难发现，两个点的LCA就是它们第一次出现的位置之间深度最小的点（证明略）。

　　所以我们用RMQ实现O（1）查询，预处理是O（n log n)

　　注意RMQ返回的是具体的点而不是深度

　　不得不提的是数据的first[x],first[y]值不一定是从小到大排的，需要判断一下（RE了很久)

　　CODE

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

using namespace std;

const int N=,P=;

struct data

{

    int to,next;

}e[N*+];

struct RMQ

{

    int num,x;

}f[P][N*+];

int head[N],first[N],n,m,root,i,j,k,tot,x,y;

inline void read(int &x)

{

    x=; char ch=getchar();

    while (ch<''||ch>'') ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

}

inline void write(int x)

{

    if (x/) write(x/);

    putchar(x%+'');

}

inline void add(int x,int y)

{

    e[++k].to=y; e[k].next=head[x]; head[x]=k;

}

inline void dfs(int k,int fa,int d)

{

    f[][++tot].num=k;

    f[][tot].x=d;

    first[k]=tot;

    for (int i=head[k];i!=-;i=e[i].next)

    if (e[i].to!=fa) dfs(e[i].to,k,d+),f[][++tot].num=k,f[][tot].x=d;

}

int main()

{

    //freopen("testdata.in","r",stdin); freopen("testdata.out","w",stdout);

    read(n); read(m); read(root);

    memset(e,-,sizeof(e));

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

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

    {

        read(x); read(y);

        add(x,y); add(y,x);

    }

    dfs(root,-,);

    for (j=;j<P;++j)

    for (i=;i+(<<j)-<=tot;++i)

    if (f[j-][i].x<f[j-][i+(<<(j-))].x) f[j][i].x=f[j-][i].x,f[j][i].num=f[j-][i].num; else f[j][i].x=f[j-][i+(<<(j-))].x,f[j][i].num=f[j-][i+(<<(j-))].num;

    while (m--)

    {

        read(x); read(y);

        x=first[x]; y=first[y];

        if (x>y) swap(x,y);

        int k=(int)log2(y-x+);

        if (f[k][x].x<f[k][y-(<<k)+].x) write(f[k][x].num); else write(f[k][y-(<<k)+].num);

        putchar('\n');

    }

    return ;

}

　　<3> Tarjan（O（n+q））

　　这个我第一次写这道题的时候已经写过了，具体看http://www.cnblogs.com/cjjsb/p/8203882.html

　　这里给一下邻接表的代码（好不容易会打）

　　CODE

#include<cstdio>

#include<cstring>

using namespace std;

const int N=;

struct data

{

    int to,next;

}e[N*+];

struct ques

{

    int to,next,num;

}q[N*+];

int head[N],qhead[N],father[N],ans[N],i,k,qk,x,y,n,m,root;

bool vis[N];

inline void read(int &x)

{

    x=; char ch=getchar();

    while (ch<''||ch>'') ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

}

inline void write(int x)

{

    if (x/) write(x/);

    putchar(x%+'');

}

inline void add(int x,int y)

{

    e[++k].to=y; e[k].next=head[x]; head[x]=k;

}

inline void qadd(int x,int y,int z)

{

    q[++qk].to=y; q[qk].num=z; q[qk].next=qhead[x]; qhead[x]=qk;

}

inline int getfather(int k)

{

    return father[k]==k?k:father[k]=getfather(father[k]);

}

inline void dfs(int k)

{

    vis[k]=;

    for (int i=qhead[k];i!=-;i=q[i].next)

    if (vis[q[i].to]) ans[q[i].num]=getfather(q[i].to);

    for (int i=head[k];i!=-;i=e[i].next)

    if (!vis[e[i].to]) dfs(e[i].to),father[e[i].to]=k;

}

int main()

{

    read(n); read(m); read(root);

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

    memset(qhead,-,sizeof(qhead));

    memset(e,-,sizeof(e));

    memset(q,-,sizeof(q));

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

    {

        read(x); read(y);

        add(x,y); add(y,x);

    }

    for (i=;i<=m;++i)

    {

        read(x); read(y);

        qadd(x,y,i); qadd(y,x,i);

    }

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

    father[i]=i;

    dfs(root);

    for (i=;i<=m;++i)

    write(ans[i]),putchar('\n');

    return ;

}

巴特西

LCA的一些算法

最新文章

热门文章