倍增做法求LCA 在 这篇博客中有提到
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N-1N−1 行每行包含两个正整数 x, yx,y，表示 xx 结点和 yy 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 MM 行每行包含两个正整数 a, ba,b，表示询问 aa 结点和 bb 结点的最近公共祖先。
输出格式
输出包含 MM 行，每行包含一个正整数，依次为每一个询问的结果。
输入输出
样例 1
输入
5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5
输出
4 4 1 4 4
说明/提示
对于 30% 的数据，N≤10，M≤10。
对于 70% 的数据，N≤10000，M≤10000。
对于 100% 的数据，N≤500000，M≤500000。
int lca(int u,int v) { while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u,v); u = fa[top[u]]; } if(dep[u] < dep[v]) return u; else return v; }
对于要求树上两个点u,v的lca，（当两个点不在一条重链上的时候）我们可以每次先让链头深depth比较大的点进行移动，不在一条重链上直接将top更深的节点跳到链头的父节点u = fa[top[u]]; ，当两个点在一条重链上的时候，从深度的角度来看，深度比较小的就应该是祖先节点
int n,m,rt; struct node { int to; int nex; } e[maxn]; int head[maxn],cnt; void init() { for(int i=0; i<maxn; i++) head[i] = -1; cnt = 0; } void add(int u,int v) { e[cnt].to = v; e[cnt].nex = head[u]; head[u] = cnt ++; } int fa[maxn],siz[maxn],son[maxn],dep[maxn],top[maxn]; void dfs1(int x) { siz[x] = 1; dep[x] = dep[fa[x]] + 1; for(int i=head[x]; ~i; i=e[i].nex) { int to = e[i].to; // fa[to] = x; if(to != fa[x]) { fa[to] = x; dfs1(to); siz[x] += siz[to]; if(siz[to] > siz[son[x]]) son[x] = to; } } } void dfs2(int rt,int tp) { top[rt] = tp; if(son[rt]) dfs2(son[rt],tp); for(int i = head[rt]; ~i; i = e[i].nex) { int to = e[i].to; if(to != fa[rt] && to != son[rt]) dfs2(to,to); } } int lca(int u,int v) { while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u,v); u = fa[top[u]]; } if(dep[u] < dep[v]) return u; else return v; } int main() { cin >> n >> m >> rt; init(); for(int i = 1; i < n; i++) { int u=read,v=read; add(u,v); add(v,u); } dfs1(rt); dfs2(rt,rt); while(m --) { int u=read,v=read; cout<<lca(u,v)<<endl; } return 0; }
