算法竞赛备考冲刺必刷题（C++） | 洛谷 P3379 【模板】最近公共祖先（LCA）

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P3379 【模板】最近公共祖先（LCA） - 洛谷

【题目描述】

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

【输入】

第一行包含三个正整数N , M , S N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。

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

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

【输出】

输出包含M MM行，每行包含一个正整数，依次为每一个询问的结果。

【输入样例】

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

【算法标签】

《洛谷 P3379 最近公共祖先（LCA）》 #最近公共祖先LCA# #模板题# #O2优化#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=500005;intn,m,s,a,b;// n: 节点数，m: 查询数，s: 根节点vector<int>e[N];// 邻接表存储树intdep[N];// 节点的深度intfa[N][20];// 倍增祖先表，fa[u][i]表示u的2^i级祖先// 深度优先搜索，预处理深度和祖先表voiddfs(intu,intfather){// 计算当前节点的深度dep[u]=dep[father]+1;// 初始化直接父节点fa[u][0]=father;// 预处理倍增祖先表for(inti=1;i<=19;i++)fa[u][i]=fa[fa[u][i-1]][i-1];// 遍历子节点for(intv:e[u])if(v!=father)// 避免走回父节点dfs(v,u);}// 求两个节点的最近公共祖先intlca(intu,intv){// 第一步：将u和v调整到同一深度if(dep[u]<dep[v])swap(u,v);// 将u向上跳，直到与v同深度for(inti=19;i>=0;i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];// 如果此时u==v，说明v是u的祖先if(u==v)returnv;// 第二步：u和v同时向上跳for(inti=19;i>=0;i--)if(fa[u][i]!=fa[v][i])// 如果祖先不同，就一起向上跳u=fa[u][i],v=fa[v][i];// 此时u和v的父节点就是LCAreturnfa[u][0];}intmain(){// 输入树的信息cin>>n>>m>>s;// 读入n-1条边for(inti=1;i<n;i++){intx,y;cin>>x>>y;e[x].push_back(y);e[y].push_back(x);}// 从根节点s开始DFS，预处理深度和祖先表dfs(s,0);// 处理m个查询for(inti=1;i<=m;i++){inta,b;cin>>a>>b;cout<<lca(a,b)<<endl;// 输出LCA}return0;}

【运行结果】

5 5 4 3 1 2 4 5 1 1 4 2 4 4 3 2 4 3 5 1 1 2 4 4 5 4