P3379 【模板】最近公共祖先（LCA）
# 【模板】最近公共祖先（LCA）
## 题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
## 输入格式
第一行包含三个正整数 $N,M,S$，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 $N-1$ 行每行包含两个正整数 $x, y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 $M$ 行每行包含两个正整数 $a, b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。
## 输出格式
输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。
## 样例 #1
### 样例输入 #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
```
## 提示
对于 $30\%$ 的数据，$N\leq 10$，$M\leq 10$。
对于 $70\%$ 的数据，$N\leq 10000$，$M\leq 10000$。
对于 $100\%$ 的数据，$1 \leq N,M\leq 500000$，$1 \leq x, y,a ,b \leq N$，**不保证** $a \neq b$。
样例说明：
该树结构如下：
第一次询问：$2, 4$ 的最近公共祖先，故为 $4$。
第二次询问：$3, 2$ 的最近公共祖先，故为 $4$。
第三次询问：$3, 5$ 的最近公共祖先，故为 $1$。
第四次询问：$1, 2$ 的最近公共祖先，故为 $4$。
第五次询问：$4, 5$ 的最近公共祖先，故为 $4$。
故输出依次为 $4, 4, 1, 4, 4$。
2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,L=19;
int n,m,s,f[N][20],head[N],k,dep[N],lo[N];
struct ed{
int to,next;
}e[2*N];
void add(int x,int y){
e[++k].to=y;
e[k].next=head[x];
head[x]=k;
}
void dfs(int x,int fa){
f[x][0]=fa;
dep[x]=dep[fa]+1;
for(int i=1;i<=19;i++)f[x][i]=f[f[x][i-1]][i-1];
for(int i=head[x];i!=0;i=e[i].next){
int to=e[i].to;
if(to!=fa)dfs(e[i].to,x);
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
while(dep[x]>dep[y]){
x=f[x][lo[dep[x]-dep[y]]];//printf("oO%d,%d,%d\n",f[x][lo[dep[x]-dep[y]]],x,y);
}
if(x==y) return x;
for(int i=19;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[y][0];
}
int main(){//printf("%d",log(1));
//memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&m,&s);
for(int i=2;i<=N;i++){
lo[i]=lo[i/2]+1;
}
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs(s,0);
//for(int i=1;i<=n;i++)printf("%d ",dep[i]);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
}
/*
5 5 4
3 1
2 4
5 1
1 4
2 4
4 2
3 4
4 2
4 5
*/
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,L=19;
int n,m,s,fa[N],head[N],k,dep[N],lo[N],ans[N];
bool vis[N];
vector<int> e[N];
vector<pair<int,int> > q[N];
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
void dfs(int x){
fa[x]=x;
vis[x]=1;
for(int i=0;i<e[x].size();i++){
int to=e[x][i];
if(!vis[to]){
dfs(to);
fa[to]=x;
}
}
for(int i=0;i<q[x].size();i++){
int c=q[x][i].first,cc=q[x][i].second;
if(vis[c]){
ans[cc]=find(c);
}
}
}
int main(){//printf("%d",log(1));
//memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
//for(int i=1;i<=n;i++)printf("%d ",dep[i]);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
q[x].push_back((pair<int,int>){y,i});
q[y].push_back((pair<int,int>){x,i});
}
vis[0]=1;
dfs(s);
for(int i=1;i<=m;i++){
printf("%d\n",ans[i]);
}
}
/*
5 5 4
3 1
2 4
5 1
1 4
2 4
4 2
3 3
2 2
4 5
*/