一.暴力解法(一)
会超时
对于点x,y。向上搜索点x节点的父节点,并将搜索到的父节点依次标记为走过,然后再搜索y节点的父节点,当搜索到第一个已经标记了的节点时,即为他们的最近的公共祖先。
题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 N,M,SN,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N-1N−1 行每行包含两个正整数 x, yx,y,表示 xx 结点和 yy 结点之间有一条直接连接的边(数据保证可以构成树)。
接下来 MM 行每行包含两个正整数 a, ba,b,表示询问 aa 结点和 bb 结点的最近公共祖先。
输出格式
输出包含 MM 行,每行包含一个正整数,依次为每一个询问的结果。
输入输出样例
输入
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出
4
4
1
4
4
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int n,m,s,a,b,p[maxn];
//p数组表示每个节点的父节点
bool vis[maxn];
vector<int> g[maxn];
//搜索找出每个节点的父节点
void dfs(int u){
int sz=g[u].size();
for(int i=0;i<sz;i++){
int v=g[u][i];
if(v==p[u]) continue;
p[v]=u;//v的父节点是u
dfs(v);
}
}
int lca(int x,int y){
memset(vis,0,sizeof vis);
while(x){//x一直向上查找到根节点,并将节点依次标记为true
vis[x]=true;
x=p[x];
}
while(!vis[y]) y=p[y];//当退出循环时,y就是最近公共祖先
return y;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){//建边时,是n-1条边
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
dfs(s);//找到每个节点的父节点
while(m--){
scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
return 0;
}
二.暴力解法(二)
会超时。
要设一个数组,表示每个节点的深度dep[i]
。根节点的深度可以从0开始,也可以从1开始。
当dep[x]<dep[y]
时,交换x和y。然后让x节点向上走,直到两个节点的深度相同dep[x]==dep[y]
。
然后当x!=y
时,让x为x的父节点,y为y的父节点,x=p[x],y=p[y]
。
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int n,m,s,a,b,p[maxn],dep[maxn];
//p数组表示每个节点的父节点
//dep数组表示每个节点的深度
vector<int> g[maxn];
//搜索找出每个节点的父节点,d表示当前节点u的深度
void dfs(int u,int d){
dep[u]=d;
int sz=g[u].size();
for(int i=0;i<sz;i++){
int v=g[u][i];
if(v==p[u]) continue;
p[v]=u;//v的父节点是u
dfs(v,d+1);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=p[x];
while(x!=y){
x=p[x];
y=p[y];
}
return x;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){//建边时,是n-1条边
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
dfs(s,0);//找到每个节点的父节点
while(m--){
scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
return 0;
}
三.倍增法
dep[u]
表示u节点的深度。f[u][i]
表示比u节点的深度小2的i次方
的那个祖先节点。就是相当于u节点的往上的第(1<<i)个祖先。
特别的,如果f[u][i]
小于所有2的i次方
,那么f[u][i]
则为根节点。f[u][i]=f[f[u][i-1]][i-1]
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int n,m,s,a,b,f[maxn][22],dep[maxn];
//dep数组表示每个节点的深度
vector<int> g[maxn];
//搜索找出每个节点的父节点,dep表示当前节点u的深度
void dfs(int u,int p,int d){
f[u][0]=p;
dep[u]=d;
int sz=g[u].size();
for(int i=0;i<sz;i++){
int v=g[u][i];
if(v==p) continue;
dfs(v,u,d+1);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=log2(dep[x]-dep[y]);i>=0;i--){
if((1<<i)<=dep[x]-dep[y]) x=f[x][i];
}
assert(dep[x]==dep[y]);
//这个函数,如果条件不符合,它会自动跳出来,然后直接停止运行,如果符合条件,则继续
if(x==y) return x;
for(int i=log2(dep[x]);i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
assert(x!=y&&f[x][0]==f[y][0]);
return f[x][0];
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){//建边时,是n-1条边
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
dfs(s,s,0);
for(int i=1;i<22;i++){
for(int u=1;u<=n;u++)
f[u][i]=f[f[u][i-1]][i-1];
}
while(m--){
scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
return 0;
}