题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入输出格式
输入格式：
第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
输出格式：
输出包含M行，每行包含一个正整数，依次为每一个询问的结果。
输入输出样例
输入样例#1：
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出样例#1：
4
4
1
4
4
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=10，M<=10
对于70%的数据：N<=10000，M<=10000
对于100%的数据：N<=500000，M<=500000
样例说明：
该树结构如下：
第一次询问：2、4的最近公共祖先，故为4。
第二次询问：3、2的最近公共祖先，故为4。
第三次询问：3、5的最近公共祖先，故为1。
第四次询问：1、2的最近公共祖先，故为4。
第五次询问：4、5的最近公共祖先，故为4。
故输出依次为4、4、1、4、4。
题解
其实是放一下代码
众所周知，LCA有几种常见的做法
- 暴力跳
- 先把较深的往上跳，跳到同一深度
- 然后一起跳
- 单次复杂度$O(n)$分分钟带你上天
- 倍增
- 在跳的时候优化一下，不一格一格的跳，而是拆分成二进制跳
- 是对暴力跳选手思维难度上最友好的升级方式
- 需要预处理出每个点往上$2^i$步的祖先，
- 时间复杂度$O(nlogn+mlogn)$，空间复杂度$O(nlogn)$
/*
qwerta
P3379 【模板】最近公共祖先（LCA）
Accepted
100
代码 C++，1.37KB
提交时间 2018-03-13 18:33:35
耗时/内存
1672ms, 51789KB
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct emm{
int f,e;
}a[];
int h[];
int d[];
int p[][];
void dfs(int no,int fa)
{
d[no]=d[fa]+;
//cout<<no<<" "<<d[no]<<" "<<fa<<endl;
p[no][]=fa;
int w;
for(w=;w<;w++)
p[no][w]=p[p[no][w-]][w-];
for(w=h[no];w;w=a[w].f)
{
if(a[w].e!=fa)
dfs(a[w].e,no);
}
return;
}
int main()
{
int c=,x,y,n,m,s,i,j;
scanf("%d%d%d",&n,&m,&s);
for(i=;i<n;++i)
{
scanf("%d%d",&x,&y);
++c;
a[c].f=h[x];
h[x]=c;
a[c].e=y;
++c;
a[c].f=h[y];
h[y]=c;
a[c].e=x;
d[i]=;
}
d[n]=;
dfs(s,);
for(i=;i<=m;++i)
{
scanf("%d%d",&x,&y);
if(d[x]<d[y])swap(x,y);
for(j=;j>=;--j)
{
if((d[x]-d[y])>=(<<j))
{
x=p[x][j];
//cout<<x<<" ";
}
}
if(x==y)printf("%d\n",x);
else{
for(j=;j>=;--j)
{
if(p[x][j]!=p[y][j])
{
x=p[x][j];
y=p[y][j];
}
}
printf("%d\n",p[x][]);}
}
/*
for(i=1;i<=n;i++)
{
cout<<i<<" ";
for(j=0;j<=19;j++)
cout<<p[i][j]<<" ";
cout<<endl;
}*/
return ;
} 倍增求LCA倍增求LCA
- ST表
- 原理：dfs序在这两点之间 的点中，深度最小的点为lca
- 所以记录dfs序和深度，在区间上找最小值，转化为RMQ问题。
- 需要预处理dfs序和ST表。
- 时间复杂度$O(n+nlogn+mlogn)$，空间复杂度$O(3*n+nlogn)$
- 理论上比倍增慢一丢丢。
/*
qwerta
P3379 【模板】最近公共祖先（LCA）
Accepted
100
代码 C++，2.28KB
提交时间 2018-06-24 11:36:03
耗时/内存
1992ms, 98929KB
*/
#include<cstdio>
using namespace std;
int n,m,s;
struct emm{
int e,f;
}a[];
int h[];
int c;
inline int read()
{
int x=;
char c=getchar();
while(c<''||c>'') c=getchar();
while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=getchar();
return x;
}
inline void write(int x)
{
if(x>) write(x/);
putchar(x%+'');
return;
}
inline int min(int qwq,int qaq){return qwq<qaq?qwq:qaq;}
inline void swap(int &qq,int &ww){int ee=qq;qq=ww;ww=ee;return;}
inline void con(int q,int w)
{
a[++c].f=h[q];
h[q]=c;
a[c].e=w;
return;
}
inline void scan()
{
n=read(),m=read(),s=read();
//scanf("%d%d%d",&n,&m,&s);
int x,y;
for(register int i=;i<n;++i)
{
x=read(),y=read();
//scanf("%d%d",&x,&y);
con(x,y);
con(y,x);
}
return;
}
int fir[];
int pl[];
int d[];
int f[][];
int dd;
void dfs(int x)
{
d[x]=++dd;
pl[++c]=x;
//printf("%d %d %d %d\n",c,x,d[c],pl[c]);
if(!fir[x])fir[x]=c;
for(register int i=h[x];i;i=a[i].f)
{
int u=a[i].e;
if(!fir[u])
{
dfs(u);
pl[++c]=x;
//printf("%d %d %d %d\n",c,x,d[c],pl[c]);
}
}
--dd;
return;
}
inline void rmq()
{
for(register int i=;i<=c;++i)
f[i][]=pl[i];
for(register int j=;(<<j)<=c;++j)
for(register int i=;i+(<<j)-<=c;++i)
{
if(d[f[i][j-]]<d[f[i+(<<(j-))][j-]])
f[i][j]=f[i][j-];
else f[i][j]=f[i+(<<(j-))][j-];
}
return;
}
inline void predo()
{
c=;
dfs(s);
rmq();
return;
}
inline void find(int x,int y)
{
int l=fir[x],r=fir[y];
if(l>r)swap(l,r);
int p;
//cout<<l<<" "<<r<<" ";
for(register int j=;j>=;--j)
if(l+(<<j)-<=r)
{
//cout<<f[l][j]<<" "<<f[r-(1<<j)+1][j]<<endl;
//cout<<l<<" "<<r<<" "<<j<<endl;
p=d[f[l][j]]<d[f[r-(<<j)+][j]]
?f[l][j]:f[r-(<<j)+][j];
//p=min(f[l][j],f[r-(1<<j)+1][j]);
write(p);putchar('\n');
return;
}
//cout<<"a"<<endl;
return;
}
inline void run()
{
for(register int i=;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
find(x,y);
}
return;
}
int main()
{
scan();
predo();
run();
return ;
}ST表求LCA
- tarjan
- 和求强连通分量的tarjan不是一个东西。
- 不太了解，应该是最小众的做法了叭，据说有常数上的优势？
- 其实以前是听懂过的，但是仗着自己已经会两种做法了就飘了没写
- 树链剖分
- 乍一听挺二了吧唧的，以前觉得像各种A+B的题解一样装哔
- 但是自从会了树剖之后我的倍增和ST表就忘光了a！（不知道该开心还是难过
- 对于会树剖的选手而言，又好写又不用过脑子还快。
- 需要预处理遍历两遍，和做一个gettop的操作，正式跑的过程应该比倍增和ST快。
- 反正我写出来快了不少。
/*
qwerta
P3379 【模板】最近公共祖先（LCA）
Accepted
100
代码 C++，1.48KB
提交时间 2018-10-09 19:16:23
耗时/内存
1043ms, 20392KB
*/
#include<cstdio>
#include<iostream>
using namespace std;
#define R register
const int MAXN=;
struct emm{
int e,f;
}a[*MAXN];
int h[MAXN];
int tot=;
void con(int x,int y)
{
a[++tot].f=h[x];
h[x]=tot;
a[tot].e=y;
a[++tot].f=h[y];
h[y]=tot;
a[tot].e=x;
return;
}
int fa[MAXN],d[MAXN],siz[MAXN],z[MAXN],top[MAXN];
void dfs(int x)
{
siz[x]=;
top[x]=x;
int mac=,macc=-;
for(R int i=h[x];i;i=a[i].f)
if(!d[a[i].e])
{
d[a[i].e]=d[x]+;
fa[a[i].e]=x;
dfs(a[i].e);
siz[x]+=siz[a[i].e];
if(siz[a[i].e]>macc){mac=a[i].e;macc=siz[a[i].e];}
}
z[x]=mac;
top[mac]=x;
return;
}
int fitop(int x)
{
if(top[x]==x)return x;
return top[x]=fitop(top[x]);
}
inline int read()
{
char ch=getchar();
int x=;
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){x=x*+ch-'';ch=getchar();}
return x;
}
void write(int x)
{
if(x>)write(x/);
putchar(x%+'');
return;
}
int main()
{
//freopen("a.in","r",stdin);
int n=read(),m=read(),s=read();
for(R int i=;i<n;++i)
{
int x=read(),y=read();
con(x,y);
}
d[s]=;
dfs(s);
for(R int i=;i<=n;++i)
top[i]=fitop(i);
for(R int c=;c<=m;++c)
{
int u=read(),v=read();
while(top[u]!=top[v])
{
if(d[top[u]]>d[top[v]])u=fa[top[u]];
else v=fa[top[v]];
}
write(d[u]<d[v]?u:v);
putchar('\n');
}
return ;
}树剖求LCA
也许还有别的做法叭，太弱了不了解。
总结
在倍增和ST之间推荐倍增，思维难度低，效率还蛮不错。
但是也见过考试考RMQ问题的...我校倍增选手当场哭出声2333
然后会了树剖还写这些个毛，多难想啊2333
其实我只是放一下代码的qwq
UPD
我校选手看过来！
这里是我下午当场出锅的代码（qaq
/*
qwerta
P3379 【模板】最近公共祖先（LCA）
Accepted
100
代码 C++，1.18KB
提交时间 2018-10-14 16:54:45
耗时/内存
2037ms, 53444KB
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define R register
struct emm{
int to,nxt;
}a[];
int h[];//邻接链表存图
int cnt=;
inline void con(int x,int y)//连边
{
a[++cnt].nxt=h[x];
h[x]=cnt;
a[cnt].to=y;
a[++cnt].nxt=h[y];
h[y]=cnt;
a[cnt].to=x;
return;
}
int fa[],d[];
void dfs(int x)//dfs建树
{
for(R int i=h[x];i;i=a[i].nxt)
if(!d[a[i].to])
{
d[a[i].to]=d[x]+;
fa[a[i].to]=x;
dfs(a[i].to);
}
return;
}
int la[][];//向上2^j步的祖先
int main()
{
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
for(R int i=;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);//读边
con(x,y);
}
d[s]=;
fa[s]=s;
dfs(s);
for(R int i=;i<=n;++i)
la[i][]=fa[i];
for(R int j=;j<=;++j)
for(R int i=;i<=n;++i)
la[i][j]=la[la[i][j-]][j-];
//cout<<endl;
for(R int i=;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
if(d[x]<d[y])swap(x,y);
//
for(R int j=;j>=;--j)
if(d[x]-(<<j)>=d[y])
x=la[x][j];
//same depth
if(x==y){printf("%d\n",y);continue;}
for(R int j=;j>=;--j)
if(la[x][j]!=la[y][j])
x=la[x][j],y=la[y][j];
//cout<<x<<" "<<y<<" "<<endl;
printf("%d\n",fa[x]);
}
return ;
}
都追到这里了要给老学姐点个关注吖！QAQ