什么是LCA？
xxxxxxxxxx
inline void bfs(){
q.push(s);
d[s] = 1;
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].to;
if(d[v]) continue;
d[v] = d[u] + 1,f[v][0] = u;
for(int j = 1; j <= t; j++) f[v][j] = f[f[v][j - 1]][j - 1];
q.push(v);
}
}
}
?
//在main函数中
t = (int)(log(n) / log(2)) + 1;
bfs();
xxxxxxxxxx
inline int lca(int &u, int &v){
if(d[u] > d[v]) swap(u, v);
for(int i = t; i >= 0; i--) if(d[f[v][i]] >= d[u]){
v = f[v][i];
}
if(u == v) return u;
for(int i = t; i >= 0; i--) if(f[u][i] != f[v][i]){
u = f[u][i];
v = f[v][i];
}
return f[u][0];
}
xxxxxxxxxx
int f[maxn][20];
xxxxxxxxxx
struct edge{
int to, next, lca;
edge(){}
edge(register const int &_to, register const int &_next){
to = _to,next = _next;
}
}qe[maxm << 1];
int qhead[maxn], qk;
?
inline void qadd(register const int &u, register const int &v){
qe[qk] = edge(v, qhead[u]);
qhead[u] = qk++;
}
?
//main函数中
memset(qhead, -1, sizeof qhead);
for(register int i = 1; i <= m; i++){
scanf("%d%d", &u, &v);
qadd(u, v),qadd(v, u);
}
xxxxxxxxxx
inline int find(register const int &x){
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}//用并查集的方式查找祖先链的顶端
?
void LCA_tarjan(int u, int pre){
vis[u] = true;
for(register int i = head[u]; ~i; i = e[i].next){
int v = e[i].to;
if(v != pre){
LCA_tarjan(v, u);
fa[v] = u;//拉祖先链
}
}
for(register int i = qhead[u]; ~i; i = qe[i].next){
v = qe[i].to;
//如果v已经拉出了祖先链，就回答询问
if(vis[v]) qe[i].lca = qe[i ^ 1].lca = find(v);
}
}
?
//main函数中
for(register int i = 1; i <= n; i++) fa[i] = i;
LCA_tarjan(s, 0);//s为根
xxxxxxxxxx
for(int i = 0; i < qk; i += 2) printf("%d\n", qe[i].lca);
xxxxxxxxxx
?
struct graph{
struct edge{
int to, next;
edge(){}
edge(const int &_to, const int &_next){
to = _to;
next = _next;
}
}e[maxm << 1];
int head[maxn], k;
inline void init(){
memset(head, -1, sizeof head);
k = 0;
}
inline void add(const int &u, const int &v){
e[k] = edge(v, head[u]);
head[u] = k++;
}
}g;
?
int fa[maxn], son[maxn], size[maxn], dep[maxn];
int dfn[maxn], id[maxn], top[maxn], cnt[maxn], tot;
int n, m, s;
?
inline void swap(int &x, int &y){int t = x; x = y; y = t;}
?
inline void dfs_getson(int u){
size[u] = 1;
for(int i = g.head[u]; ~i; i = g.e[i].next){
int v = g.e[i].to;
if(v == fa[u]) continue;
dep[v] = dep[u] + 1;
fa[v] = u;
dfs_getson(v);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
?
inline void dfs_rewrite(int u, int tp){
top[u] = tp;
dfn[u] = ++tot;
id[tot] = u;
if(son[u]) dfs_rewrite(son[u], tp);
for(int i = g.head[u]; ~i; i = g.e[i].next){
int v = g.e[i].to;
if(v != son[u] && v != fa[u]) dfs_rewrite(v, v);
}
cnt[u] = tot;
}
?
inline int lca(int u, int v){
while(top[u] != top[v]){
if(dep[top[u]] > dep[top[v]]) swap(u, v);
v = fa[top[v]];
}
if(dep[u] > dep[v]) swap(u, v);
return u;
}
?
int main(){
g.init();
scanf("%d%d%d", &n, &m, &s);
for(int i = 1; i < n; i++){
int u, v;
scanf("%d%d", &u, &v);
g.add(u, v);
g.add(v, u);
}
dfs_getson(s);
dfs_rewrite(s, s);
for(int i = 1; i <= n; i++){
int u, v;
scanf("%d%d", &u, &v);
printf("%d\n", lca(u, v));
}
return 0;
}
原文：https://www.cnblogs.com/akura/p/10808772.html