题解 P3379 【【模板】最近公共祖先(LCA)】

hicc0305

2018-05-07 20:59:03

Solution

在这里介绍两种方法: ### 一、RMQ求LCA 先介绍一下三个数组的含义 ver[i]表示dfs第i个访问的结点 R[i]表示ver[i]所在的层数,也就是深度 first[i]表示ver[i]第一次出现的下标 举个栗子如下图 ![](https://cdn.luogu.com.cn/upload/pic/18791.png) 求出来的三个数组如下图,f->first,v->ver,T就是点的编号 ![](https://cdn.luogu.com.cn/upload/pic/18792.png) 如果我们要求d和f的LCA,我们发现d第一次出现在4,f第一次出现在9,由dfs的性质可以知道,在4~9之间深度最小的点就是LCA 于是,我们可以用ST表来处理出各区间之间深度的RMQ,这样就可以对于每个询问只用常数的时间就能输出答案,并且预处理也只用nlogn,按照道理来说是比倍增要快的。可是。。。我发现不加读入优化就很悬。。时间卡的很紧,读入输出都要尽量优。。不要像我一开始用cout。。。好了,不扯淡了 上代码 ```cpp #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,s,tot=0,cnt=0; int head[1000100],nxt[1000100],to[1000100]; int fir[1000100],ver[1000100],r[1000100]; int f[20][1000100],rec[20][1000100]; int read() { int x=0,flag=0; char ch=getchar(); if(ch=='-') flag=1; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar(); if(flag) return -x; return x; } void addedge(int x,int y) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; } void dfs(int u,int dep)//dfs处理出三个数组 { fir[u]=++tot,ver[tot]=u,r[tot]=dep; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(!fir[v]) { dfs(v,dep+1); ver[++tot]=u,r[tot]=dep; } } } int main() { memset(head,-1,sizeof(head)); n=read(),m=read(),s=read(); for(int i=1;i<n;i++) { int x,y; x=read(),y=read(); addedge(x,y); addedge(y,x); } dfs(s,1); //ST表求RMQ,不会ST表的童鞋先去做一下ST表模板。。。 for(int i=1;i<=tot;i++) f[0][i]=r[i],rec[0][i]=ver[i]; for(int i=1;i<=log(tot)/log(2);i++) for(int j=1;j<=tot-(1<<i)+1;j++) { if(f[i-1][j]<f[i-1][j+(1<<(i-1))]) f[i][j]=f[i-1][j],rec[i][j]=rec[i-1][j]; else f[i][j]=f[i-1][j+(1<<(i-1))],rec[i][j]=rec[i-1][j+(1<<(i-1))]; } //rec记录的是区间内深度最小值的编号 for(int i=1;i<=m;i++) { int l,r; l=read(),r=read(); l=fir[l],r=fir[r]; if(l>r) swap(l,r); int k=0; while((1<<k)<=r-l+1) k++; k--; if(f[k][l]<f[k][r-(1<<k)+1]) printf("%d\n",rec[k][l]); else printf("%d\n",rec[k][r-(1<<k)+1]);//常见的ST表输出 } return 0; } ``` ### 二、倍增求LCA 这里就不在详细介绍了,因为楼下的大佬们基本都是用倍增的,有很详细的解释。 还是简单说一下吧。简单的来说,就是两个点一起爬树,先让深度比较深的点爬到和低的点一样的位置,然后再开始一起爬,爬到两个点重合就是LCA 代码如下: ```cpp #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,s,tot=0,cnt=0; int head[1000100],nxt[1000100],to[1000100]; int d[500100],f[30][1000100]; int read() { int x=0,flag=0; char ch=getchar(); if(ch=='-') flag=1; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar(); if(flag) return -x; return x; } void addedge(int x,int y) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; } void dfs(int u,int dep)//处理出各个点的深度 { d[u]=dep; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(!d[v]) dfs(v,dep+1),f[0][v]=u; } } int LCA(int x,int y) { int l=0; while((1<<l)<=n) l++; l--;//l表示的是最大的i为多少,当然,不用求l也可以,只要是一个够大的数像20即可 if(d[x]<d[y]) swap(x, y);//让x为深度较大的 for(int i=20;i>=0;i--) if(d[y]<=d[x]-(1<<i)) x=f[i][x];//不断爬树,使深度相同 if(x==y) return x; for(int i=20;i>=0;i--) { if(f[i][x]!=f[i][y])//不同就一起爬树 { x=f[i][x]; y=f[i][y]; } } return f[0][x]; } int main() { memset(head,-1,sizeof(head)); n=read(),m=read(),s=read(); for(int i=1;i<n;i++) { int x,y; x=read(),y=read(); addedge(x,y); addedge(y,x); } f[0][s]=s; dfs(s,1); for(int i=1;(1<<i)<=n;i++) for(int j=1;j<=n;j++) f[i][j]=f[i-1][f[i-1][j]];//f[i][j] 表示 j的2^i 倍祖先,所以f[0][v]就是v的父亲节点u for(int i=1;i<=m;i++) { int l,r; l=read(),r=read(); printf("%d\n",LCA(l,r)); } return 0; } ``` ### 三、tarjan求LCA 其实没有了,吓吓你的而已,但确实有这种算法。tarjan是真的巨。。大家可以百度一下我这里真的就不介绍了。