给定一棵 以 sss 为根节点，共有 nnn 个点的树。
有 mmm 次查询 每次查询 u,vu ,vu,v 的最近公共祖先。
算法流程
111.根据连边的信息建图（邻接表）。代码就不贴了，注意建立双向边。
222.dfs1dfs1dfs1 ，从给定的起点出发，预处理以下信息：
①①①深度：deep[e[i].to]=deep[x]+1deep[e[i].to] = deep[x]+1deep[e[i].to]=deep[x]+1
②②②父亲：fa[e[i].to]=xfa[e[i].to] = xfa[e[i].to]=x
③③③大小：size[x]+=dfs1(e[i].to)size[x] += dfs1(e[i].to)size[x]+=dfs1(e[i].to)
子树大小无法直接求得，因为该点向下遍历多少点是无法从当前状态求出的。所以我们可以考虑递归回溯来解决。在遍历前自己本身大小为 size[x]=1size[x]=1size[x]=1 。我们只需要加上遍历到的下一个点的大小即可，所以处理好深度和父亲的信息后，只需回溯 returnreturnreturn size[x]size[x]size[x]
④④④儿子：if(size[e[i].to]>size[son[x]])son[x]=e[i].toif(size[e[i].to] > size[son[x]]) son[x] = e[i].toif(size[e[i].to]>size[son[x]])son[x]=e[i].to
链剖法每个点记录的儿子是子树大小最大的点。该记录的最好方式是降低期望查询的时间复杂度，使得查询效率尽可能加快。
dfs1(s);
int dfs1(int x)
{
size[x] = 1;
for(int i = head[x]; i; i = e[i].nxt)
{
if(deep[e[i].to]) continue;
deep[e[i].to] = deep[x] + 1;
fa[e[i].to] = x;
size[x] += dfs1(e[i].to);
if(size[e[i].to] > size[son[x]]) son[x] = e[i].to;
}
return size[x];
}
3.dfs2dfs2dfs2：通过 dfs1dfs1dfs1 预处理后，除叶子节点以外，都记录了儿子。若从树根开始按照 son[x]son[x]son[x] 的顺序向下遍历，一定是遍历了一条链，而且沿途所有点的链头都是第一个被遍历的点。 son[x]son[x]son[x] 遍历结束回溯的时候，可以继续找下一个儿子节点继续按这个儿子节点的 son[e[i].to]son[e[i].to]son[e[i].to] 又挖出一条链来。
如此流程，原来的树就会被拆成若干条链，每条链的每个点都记录的自己的链头元素。为下一步查询做准备。
dfs2(s, s)
void dfs2(int x, int root)
{
top[x] = root;
if(son[x]) dfs2(son[x], root);
for(int i = head[x]; i; i = e[i].nxt)
if(e[i].to != son[x] && e[i].to != fa[x])
dfs2(e[i].to, e[i].to);
}
444.查询：对于要查询的 lca(u,v)lca(u, v)lca(u,v) ，有两种情况：
①①①两点在同一条链上，即 top[u]=top[v]top[u] = top[v]top[u]=top[v]。此时深度小的点即为 lcalcalca。
②②②两点不在同一条链上，即 top[u]≠top[v]top[u] \neq top[v]top[u]=top[v] 。此时 两点中记录的链头的深度较深的点，应跳出此链，到下一条链，然后再次查询新的两点的 lcalcalca。即若 deep[top[v]]>deep[top[u]]deep[top[v]] > deep[top[u]]deep[top[v]]>deep[top[u]] , v=fa[top[v]]v = fa[top[v]]v=fa[top[v]]
query_lca(u, v);
int query_lca(int u, int v)
{
while(top[u] != top[v])
{
if(deep[top[u]] > deep [top[v]]) swap(u, v);
v = fa[top[v]];
}
return deep[u] > deep[v] ? v : u;
}
完整代码：
#include
#include
#include
#include
#include
#include
using namespace std;
int n, m, s;
int head[1001010],deep[1001010],size[1010100],fa[1010100],son[1010100],top[1101010];
struct list
{
int to,nxt;
}e[1010101];
int read()
{
int rt = 0, in = 1; char ch = getchar();
while(ch '9') {if(ch == '-') in = -1; ch = getchar();}
while(ch >= '0' && ch size[son[x]]) son[x] = e[i].to;
}
return size[x];
}
void dfs2(int x, int root)
{
top[x] = root;
if(son[x]) dfs2(son[x], root);
for(int i = head[x]; i; i = e[i].nxt)
if(e[i].to != son[x] && e[i].to != fa[x])
dfs2(e[i].to, e[i].to);
}
int query_lca(int u, int v)
{
while(top[u] != top[v])
{
if(deep[top[u]] > deep [top[v]]) swap(u, v);
v = fa[top[v]];
}
return deep[u] > deep[v] ? v : u;
}
int main()
{
n = read(), m = read(), s = read();
for(int i = 1; i < n; i++)
{
int u = read(), v = read();
add_edge(u, v), add_edge(v, u);
}
deep[s] = 1;
dfs1(s);
dfs2(s, s);
for(int i = 1; i <= m; i++)
{
int u = read(), v = read();
printf("%d\n",query_lca(u, v));
}
system("pause");
return 0;
}
练习题：
[模版] lca
luogu P3398