85 lines
1.6 KiB
C++
85 lines
1.6 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
const int N = 500001;
|
||
|
||
struct Edge {
|
||
int to;
|
||
int nxt;
|
||
} e[2*N];
|
||
|
||
int n,m,s;
|
||
int depth[N], Log[N];
|
||
int dbl[N][20]; //倍增数组
|
||
int head[N], tot;
|
||
|
||
void addEdge(int x,int y) {
|
||
e[++tot].to=y;
|
||
e[tot].nxt=head[x];
|
||
head[x]=tot;
|
||
}
|
||
|
||
void dfs(int cur, int fa) {
|
||
depth[cur]=depth[fa]+1;
|
||
dbl[cur][0]=fa;
|
||
for(int i=1; (1<<i) < depth[cur]; i++) {
|
||
int mid = dbl[cur][i-1];
|
||
dbl[cur][i]=dbl[mid][i-1]; // 计算倍增数组
|
||
}
|
||
|
||
for(int i=head[cur]; i>0; i=e[i].nxt) {
|
||
if(e[i].to != fa) // 遍历子节点
|
||
dfs(e[i].to, cur);
|
||
}
|
||
}
|
||
|
||
int lca(int x,int y) {
|
||
// 把两个点升至同一高度，再一起跳
|
||
if(depth[x]<depth[y]) { // 规定x更深
|
||
swap(x,y);
|
||
}
|
||
|
||
while(depth[x]>depth[y]) {
|
||
x=dbl[x][Log[depth[x]-depth[y]]];
|
||
}
|
||
|
||
if(x==y)
|
||
return x;
|
||
|
||
// 两个点同时往上跳，跳到LCA的下一层为止
|
||
for(int i=Log[depth[x]]; i>=0; i--)
|
||
if(dbl[x][i] != dbl[y][i]) {
|
||
x=dbl[x][i];
|
||
y=dbl[y][i];
|
||
}
|
||
|
||
return dbl[x][0];
|
||
}
|
||
|
||
/*
|
||
倍增算法时间复杂度是O(nlogn)
|
||
*/
|
||
int main() {
|
||
scanf("%d%d%d",&n,&m,&s);
|
||
for(int i=1; i<=n-1; i++) {
|
||
int x,y;
|
||
scanf("%d%d",&x,&y);
|
||
addEdge(x,y);
|
||
addEdge(y,x);
|
||
}
|
||
dfs(s,0); // 建树
|
||
|
||
// 预处理，常数优化
|
||
for(int i=2; i<=n; i++) {
|
||
Log[i]=Log[i>>1] + 1;
|
||
}
|
||
|
||
for(int i=1; i<=m; i++) {
|
||
int x, y;
|
||
scanf("%d%d", &x, &y);
|
||
printf("%d\n", lca(x, y));
|
||
}
|
||
return 0;
|
||
}
|
||
|