洛谷上的lca模板题——传送门
1.tarjan求lca
学了求lca的tarjan算法（离线），在洛谷上做模板题，结果后三个点超时。
又把询问改成链式前向星，才ok。
这个博客，tarjan分析的很详细。
附代码——
#include <cstdio>
#include <cstring> const int maxn = ; int n, m, cnt, s, cns;
int x, y, z[maxn];//z是x和y的lca
int f[maxn], head[maxn], from[maxn];
bool vis[maxn];
struct node
{
int to, next;
}e[ * maxn];
struct Node
{
int to, next, num;
}q[ * maxn]; inline int read()//读入优化
{
int x = , f = ;
char ch = getchar();
while(ch < '' || ch > '')
{
if(ch == '-') f = -;
ch = getchar();
}
while(ch >= '' && ch <= '')
{
x = x * + ch - '';
ch = getchar();
}
return x * f;
} inline void ask(int u, int v, int i)//储存待询问的结构体，也是链式前向星优化
{
q[cns].num = i;//num表示第几次询问
q[cns].to = v;
q[cns].next = from[u];
from[u] = cns++;
} inline void add(int u, int v)//
{
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt++;
} inline int find(int a)
{
return a == f[a] ? a : f[a] = find(f[a]);//路径压缩优化
} /*inline void Union(int a, int b)
{
int fx = find(a), fy = find(b);
if(fx == fy) return;
f[fy] = fx;
}*/ inline void tarjan(int k)
{
int i, j;
vis[k] = ;
f[k] = k;
for(i = head[k]; i != -; i = e[i].next)
if(!vis[e[i].to])
{
tarjan(e[i].to);
//Union(k, e[i].to);
f[e[i].to] = k;
}
for(i = from[k]; i != -; i = q[i].next)
if(vis[q[i].to] == )
z[q[i].num] = find(q[i].to);
} int main()
{
int i, j, u, v;
n = read();
m = read();
s = read();
memset(head, -, sizeof(head));
memset(from, -, sizeof(from));
for(i = ; i <= n - ; i++)
{
u = read();
v = read();
add(u, v);//注意添加两遍
add(v, u);
}
for(i = ; i <= m; i++)
{
x = read();
y = read();
ask(x, y, i);//两遍
ask(y, x, i);
}
tarjan(s);
for(i = ; i <= m; i++) printf("%d\n", z[i]);
return ;
}
进过培训，修改了代码
# include <iostream>
# include <cstdio>
# include <cstring>
# include <string>
# include <cmath>
# include <vector>
# include <map>
# include <queue>
# include <cstdlib>
# define MAXN
using namespace std; inline int get_num() {
int k = , f = ;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -;
for(; isdigit(c); c = getchar()) k = k * + c - '';
return k * f;
} int n, m, s;
int fa[MAXN], qx[MAXN], qy[MAXN], ans[MAXN], f[MAXN];
vector <int> vec[MAXN], q[MAXN]; inline int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
} inline void dfs(int u)
{
int i, v;
fa[u] = u;
for(i = ; i < vec[u].size(); i++)
{
v = vec[u][i];
if(f[u] != v) f[v] = u, dfs(v);
}
for(i = ; i < q[u].size(); i++)
if(f[v = u ^ qx[q[u][i]] ^ qy[q[u][i]]])
ans[q[u][i]] = find(v);
fa[u] = f[u];
} int main()
{
int i, x, y;
n = get_num();
m = get_num();
s = get_num();
for(i = ; i < n; i++)
{
x = get_num();
y = get_num();
vec[x].push_back(y);
vec[y].push_back(x);
}
for(i = ; i <= m; i++)
{
qx[i] = get_num();
qy[i] = get_num();
q[qx[i]].push_back(i);
q[qy[i]].push_back(i);
}
dfs(s);
for(i = ; i <= m; i++) printf("%d\n", ans[i]);
return ;
}
其实上面两个代码有些重复运算，请手动把求lca的过程放到dfs上面（也就是遍历到这个节点就求lca，而不是遍历完再求）
2.倍增求lca
下面是求lca的倍增算法（在线）。
1. DFS预处理出所有节点的深度和父节点
inline void dfs(int u)
{
int i;
for(i=head[u];i!=-;i=next[i])
{
if (!deep[to[i]])
{
deep[to[i]] = deep[u]+;
p[to[i]][] = u; //p[x][0]保存x的父节点为u;
dfs(to[i]);
}
}
}
dfs预处理
2. 初始各个点的2^j祖先是谁 ,其中 2^j (j =0...log(该点深度))倍祖先，1倍祖先就是父亲，2倍祖先是父亲的父亲......。
void init()
{
int i,j;
//p[i][j]表示i结点的第2^j祖先
for(j=;(<<j)<=n;j++)
for(i=;i<=n;i++)
if(p[i][j-]!=-)
p[i][j]=p[p[i][j-]][j-];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先
}
初始化
3.从深度大的节点上升至深度小的节点同层，如果此时两节点相同直接返回此节点，即lca。
否则，利用倍增法找到最小深度的 p[a][j]!=p[b][j]，此时他们的父亲p[a][0]即lca。
int lca(int a,int b)//最近公共祖先
{
int i,j;
if(deep[a]<deep[b])swap(a,b);
for(i=;(<<i)<=deep[a];i++);
i--;
//使a，b两点的深度相同
for(j=i;j>=;j--)
if(deep[a]-(<<j)>=deep[b])
a=p[a][j];
if(a==b)return a;
//倍增法，每次向上进深度2^j，找到最近公共祖先的子结点
for(j=i;j>=;j--)
{
if(p[a][j]!=-&&p[a][j]!=p[b][j])
{
a=p[a][j];
b=p[b][j];
}
}
return p[a][];
}
倍增求lca
最后是完整代码，为了节约时间，就没有把p数组初始化为-1.
#include <cstdio>
#include <cstring>
#include <iostream> const int maxn = ;
int n, m, cnt, s;
int next[ * maxn], to[ * maxn], head[ * maxn], deep[maxn], p[maxn][]; inline void add(int x, int y)
{
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
} inline void dfs(int i)
{
int j;
for(j = head[i]; j != -; j = next[j])
if(!deep[to[j]])
{
deep[to[j]] = deep[i] + ;
p[to[j]][] = i;
dfs(to[j]);
}
} inline void init()
{
int i, j;
for(j = ; ( << j) <= n; j++)
for(i = ; i <= n; i++)
p[i][j] = p[p[i][j - ]][j - ];
} inline int lca(int a, int b)
{
int i, j;
if(deep[a] < deep[b]) std::swap(a, b);
for(i = ; ( << i) <= deep[a]; i++);
i--;
for(j = i; j >= ; j--)
if(deep[a] - ( << j) >= deep[b])
a = p[a][j];
if(a == b) return a;
for(j = i; j >= ; j--)
if(p[a][j] != p[b][j])
{
a = p[a][j];
b = p[b][j];
}
return p[a][];
} int main()
{
int i, j, x, y;
memset(head, -, sizeof(head));
scanf("%d %d %d", &n, &m, &s);
for(i = ; i <= n - ; i++)
{
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
deep[s] = ;
dfs(s);
init();
for(i = ; i <= m; i++)
{
scanf("%d %d", &x, &y);
printf("%d\n", lca(x, y));
}
return ;
}
经过培训，又改了改代码。
# include <iostream>
# include <cstdio>
# include <cstring>
# include <string>
# include <cmath>
# include <vector>
# include <map>
# include <queue>
# include <cstdlib>
# define MAXN
using namespace std; inline int get_num() {
int k = , f = ;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -;
for(; isdigit(c); c = getchar()) k = k * + c - '';
return k * f;
} int n, m, s;
int f[MAXN][], deep[MAXN];
vector <int> vec[MAXN]; inline void dfs(int u)
{
int i, v;
deep[u] = deep[f[u][]] + ;
for(i = ; f[u][i]; i++) f[u][i + ] = f[f[u][i]][i];
for(i = ; i < vec[u].size(); i++)
{
v = vec[u][i];
if(!deep[v]) f[v][] = u, dfs(v);
}
} inline int lca(int x, int y)
{
int i;
if(deep[x] < deep[y]) swap(x, y);
for(i = ; i >= ; i--)
if(deep[f[x][i]] >= deep[y])
x = f[x][i];
if(x == y) return x;
for(i = ; i >= ; i--)
if(f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][];
} int main()
{
int i, x, y;
n = get_num();
m = get_num();
s = get_num();
for(i = ; i < n; i++)
{
x = get_num();
y = get_num();
vec[x].push_back(y);
vec[y].push_back(x);
}
dfs(s);
for(i = ; i <= m; i++)
{
scanf("%d %d", &x, &y);
printf("%d\n", lca(x, y));
}
return ;
}
3.树剖法求lca
# include <iostream>
# include <cstdio>
# include <cstring>
# include <string>
# include <cmath>
# include <vector>
# include <map>
# include <queue>
# include <cstdlib>
# define MAXN
using namespace std; inline int get_num() {
int k = , f = ;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -;
for(; isdigit(c); c = getchar()) k = k * + c - '';
return k * f;
} int n, m, s;
int f[MAXN], size[MAXN], top[MAXN], son[MAXN], deep[MAXN];
vector <int> vec[MAXN]; inline void dfs1(int u)
{
int i, v;
size[u] = ;
deep[u] = deep[f[u]] + ;
for(i = ; i < vec[u].size(); i++)
{
v = vec[u][i];
if(!deep[v])
{
f[v] = u;
dfs1(v);
size[u] += size[v];
if(size[son[u]] < size[v]) son[u] = v;
}
}
} inline void dfs2(int u, int tp)
{
int i, v;
top[u] = tp;
if(!son[u]) return;
dfs2(son[u], tp);
for(i = ; i < vec[u].size(); i++)
{
v = vec[u][i];
if(v != son[u] && v != f[u]) dfs2(v, v);
}
} inline int lca(int x, int y)
{
while(top[x] != top[y])
{
if(deep[top[x]] < deep[top[y]]) swap(x, y);
x = f[top[x]];
}
if(deep[x] > deep[y]) swap(x, y);
return x;
} int main()
{
int i, x, y;
n = get_num();
m = get_num();
s = get_num();
for(i = ; i < n; i++)
{
x = get_num();
y = get_num();
vec[x].push_back(y);
vec[y].push_back(x);
}
dfs1(s);
dfs2(s, s);
for(i = ; i <= m; i++)
{
x = get_num();
y = get_num();
printf("%d\n", lca(x, y));
}
return ;
}