【模板】最近公共祖先（LCA）【牛客tracker 每日一题】

【模板】最近公共祖先（LCA）

时间限制：3秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

给定一棵由N NN个点组成的以点R RR为根的多叉树，有M MM次询问，每次给定两个节点u , v u,vu,v，你需要求出这两个节点的最近公共祖先。

【名词解释】

最近公共祖先（L C A LCALCA）：两个节点在树中深度最大的共同祖先节点。

输入描述：

第一行包含三个正整数N , M , R ( 1 ≦ R ≦ N ≤ 5 × 10 5 , 1 ≦ M ≦ 5 × 10 5 ) N,M,R(1≦R≦N≤5×10^5,1≦M≦5×10^5)N,M,R(1≦R≦N≤5×105,1≦M≦5×105)，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N − 1 N−1N−1行每行包含两个正整数x , y x,yx,y，表示x xx结点和y yy结点之间有一条直接连接的边（数据保证可以构成树）。

接下来M MM行每行包含两个正整数a , b （ 1 ≦ a , b ≦ N ） a,b（1≦a,b≦N）a,b（1≦a,b≦N），表示询问a aa结点和b bb结点的最近公共祖先。

输出描述：

输出包含M 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

说明：

该树结构如下：

第一次询问：2 , 4 2,42,4的最近公共祖先，故为4 44。

第二次询问：3 , 2 3,23,2的最近公共祖先，故为4 44。

第三次询问：3 , 5 3,53,5的最近公共祖先，故为1 11。

第四次询问：1 , 2 1,21,2的最近公共祖先，故为4 44。

第五次询问：4 , 5 4,54,5的最近公共祖先，故为4 44。

故输出依次为4 , 4 , 1 , 4 , 4 4,4,1,4,44,4,1,4,4。

解题思路

本题是最近公共祖先(LCA)模板题，针对N , M ≤ 5 × 10 5 N,M \le 5 \times 10^5N,M≤5×105的大数据规模，采用倍增法实现高效求解。暴力法时间复杂度过高无法通过，倍增法通过预处理每个节点的2 k 2^k2k级祖先与节点深度，将单次查询复杂度降至O ( log ⁡ N ) O(\log N)O(logN)。首先构建树的邻接表，通过DFS递归遍历整棵树，初始化父节点与倍增数组；查询时，先将两个节点跳至同一深度，再同步倍增上跳，直至找到最近公共祖先。算法预处理复杂度O ( N log ⁡ N ) O(N \log N)O(NlogN)，整体效率完美适配题目数据约束。

总结

核心逻辑：倍增法预处理节点的多级祖先信息，通过快速跳步实现LCA的高效查询。
关键操作：邻接表建图、DFS预处理深度与倍增表、深度对齐+倍增跳步求解。
效率保障：对数级的预处理与查询复杂度，轻松应对5 × 10 5 5 \times 10^55×105级别的节点与询问数量。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=500010;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll LOG=25;ll n,m,r;vector<ll>g[N];ll depth[N];ll st[N][LOG];voiddfs(ll u,ll p){st[u][0]=p;for(ll i=1;i<LOG;i++){st[u][i]=st[st[u][i-1]][i-1];}for(ll i:g[u]){if(i==p){continue;}depth[i]=depth[u]+1;dfs(i,u);}}llLCA(ll u,ll v){if(depth[u]<depth[v])swap(u,v);ll diff=depth[u]-depth[v];for(ll i=0;i<LOG;i++){if(diff&(1LL<<i))u=st[u][i];}if(u==v)returnu;for(ll i=LOG-1;i>=0;i--){if(st[u][i]!=st[v][i]){u=st[u][i];v=st[v][i];}}returnst[u][0];}voidsolve(){cin>>n>>m>>r;for(ll i=1;i<n;i++){ll x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}depth[r]=0;dfs(r,r);while(m--){ll x,y;cin>>x>>y;cout<<LCA(x,y)<<endl;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}