【模板】最近公共祖先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,b1≦a,b≦Na,b1≦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级别的节点与询问数量。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N500010;constll INF1e18;constll M1e610;constll mod1e97;constll LOG25;ll n,m,r;vectorllg[N];ll depth[N];ll st[N][LOG];voiddfs(ll u,ll p){st[u][0]p;for(ll i1;iLOG;i){st[u][i]st[st[u][i-1]][i-1];}for(ll i:g[u]){if(ip){continue;}depth[i]depth[u]1;dfs(i,u);}}llLCA(ll u,ll v){if(depth[u]depth[v])swap(u,v);ll diffdepth[u]-depth[v];for(ll i0;iLOG;i){if(diff(1LLi))ust[u][i];}if(uv)returnu;for(ll iLOG-1;i0;i--){if(st[u][i]!st[v][i]){ust[u][i];vst[v][i];}}returnst[u][0];}voidsolve(){cinnmr;for(ll i1;in;i){ll x,y;cinxy;g[x].push_back(y);g[y].push_back(x);}depth[r]0;dfs(r,r);while(m--){ll x,y;cinxy;coutLCA(x,y)endl;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}