本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：[P10289 GESP样题 八级] 小杨的旅游 - 洛谷
【题目描述】
小杨准备前往 B 国旅游。
B 国有n nn座城市，这n nn座城市依次以1 11至n nn编号。城市之间由n − 1 n-1n−1条双向道路连接，任意两座城市之间均可达（即任意两座城市之间存在可达的路径）。
小杨可以通过双向道路在城市之间移动，通过一条双向道路需要1 11单位时间。
B 国城市中有k kk座城市设有传送门。设有传送门的城市的编号依次为b 1 , b 2 , ⋯ , b k b_1,b_2, \cdots ,b_kb1,b2,⋯,bk。小杨可以从任意一座设有传送门的城市花费0 00单位时间前往另一座设有传送门的城市。
注：如果两座设有传送门的城市之间存在双向道路，那么小杨可以选择通过双向道路移动，也可以选择通过传送门传送。
小杨计划在 B 国旅游q qq次。第i ii次旅游（1 ≤ i ≤ q 1 \le i \le q1≤i≤q），⼩杨计划从编号为u i u_iui的城市前往编号为v i v_ivi的城市，小杨希望你能求出所需要的最短时间。
【输入】
第一行包含三个正整数n , k , q n,k,qn,k,q，分别表示 B 国的城市数量，设有传送门的城市数量，以及小杨计划在 B 国旅游的次数。
接下来n − 1 n-1n−1行，每行包含两个正整数x i , y i x_i, y_ixi,yi，表示一条双向道路连接的两座城市的编号。
第n + 1 n + 1n+1行包含k kk个正整数，表示设有传送门的城市的编号。
接下来q qq行，每行包含两个正整数u i , v i u_i,v_iui,vi，表示小杨第i ii次旅游行程的起点城市编号与终点城市编号。
【输出】
输出共q qq行。第i ii行（1 ≤ i ≤ q 1 \leq i \leq q1≤i≤q）输出一个非负整数，表示小杨计划第i ii次旅游从编号为u i u_iui的城市前往编号为v i v_ivi的城市所需要的最短时间。
【输入样例】
7 2 1 5 7 3 6 2 3 1 5 5 4 1 2 7 4 3 7【输出样例】
4【算法标签】
《洛谷 P10289 小杨的旅游》 #广度优先搜索BFS# #最短路# #最近公共祖先LCA# #GESP#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=200005,M=N*2;// N: 最大节点数, M: 最大边数typedefpair<int,int>PII;// 定义pair类型，用于存储节点和步数intn,k,Q;// n: 节点数, k: 特殊节点数, Q: 查询次数inth[N],e[M],ne[M],idx;// 邻接表存储树intdep[N],dep2[N],fa[N][30];// dep: 节点深度, dep2: 到最近特殊节点的距离, fa: 倍增祖先表boolst[N];// 标记数组，用于BFS2queue<int>q;// BFS队列queue<PII>q2;// 多源BFS队列// 添加无向边voidadd(inta,intb){e[idx]=b,ne[idx]=h[a],h[a]=idx++;// 添加边a->b}// 预处理节点深度和倍增祖先表voidbfs(introot){memset(dep,0x3f,sizeof(dep));// 初始化为无穷大dep[0]=0,dep[root]=1;// 虚拟0节点深度为0, 根节点深度为1q.push(root);while(!q.empty())// 计算节点深度{intt=q.front();q.pop();for(inti=h[t];i!=-1;i=ne[i])// 遍历节点t的所有邻接点{intj=e[i];// 邻接节点jif(dep[j]>dep[t]+1)// 如果j的深度还未计算{dep[j]=dep[t]+1;// 计算j的深度q.push(j);// j入队fa[j][0]=t;// j向上走2^0=1步即为父节点tfor(intk=1;k<=29;k++)// 递推计算fa[j][k]{// j向上走2^k步等于j向上走2^(k-1)步后, 再向上走2^(k-1)步fa[j][k]=fa[fa[j][k-1]][k-1];}}}}}// LCA倍增算法，计算节点x和节点y的最近公共祖先intlca(intx,inty){if(dep[x]<dep[y])swap(x,y);// 保证x为深度较大的节点// 步骤1：把节点x向上跳，直到与节点y深度相同for(intk=29;k>=0;k--)// 从高位向低位尝试if(dep[fa[x][k]]>=dep[y])x=fa[x][k];// 如果跳2^k步后深度仍大于等于y, 就跳if(x==y)returnx;// 如果x和y已经相同, 则找到LCA// 步骤2：两个节点同时向上跳，跳到公共祖先的下一层for(intk=29;k>=0;k--){if(fa[x][k]!=fa[y][k])// 如果跳2^k步后祖先不同, 就都跳上去{x=fa[x][k];y=fa[y][k];}}returnfa[x][0];// 返回x或y的父节点, 即为最近公共祖先}// 多源BFS，计算每个节点到最近特殊节点的距离voidbfs2(){while(!q2.empty()){intu=q2.front().first;// 当前节点intstep=q2.front().second;// 到起点的距离// cout << "u step " << u << " " << step << endl;q2.pop();for(inti=h[u];i!=-1;i=ne[i])// 遍历u的所有邻接节点{intj=e[i];// 邻接节点jif(st[j])continue;// 如果j已访问，跳过dep2[j]=step+1;// 更新j到最近特殊节点的距离q2.push({j,step+1});// j入队st[j]=1;// 标记j已访问}}}intmain(){cin>>n>>k>>Q;// 输入节点数、特殊节点数、查询次数memset(h,-1,sizeof(h));// 初始化邻接表// 输入n-1条边，构建树for(inti=1;i<n;i++){intx,y;cin>>x>>y;add(x,y),add(y,x);// 添加无向边}// 初始化特殊节点for(inti=1;i<=k;i++){intx;cin>>x;// 输入特殊节点编号dep2[x]=0;// 特殊节点到自身的距离为0q2.push({x,0});// 特殊节点入队st[x]=1;// 标记特殊节点已访问}bfs(1);// 从节点1开始BFS，预处理深度和祖先表// 调试输出深度// for (int i=1; i<=n; i++)// cout << dep[i] << " ";// cout << endl;bfs2();// 多源BFS，计算每个节点到最近特殊节点的距离// 处理Q个查询while(Q--){intx,y;cin>>x>>y;// 输入查询的两个节点inttmp=lca(x,y);// 计算x和y的最近公共祖先intans;if(k!=0)// 如果有特殊节点// 两种走法的较小值：// 1. 直接走树边：x到y的距离 = dep[x] + dep[y] - 2*dep[tmp]// 2. 通过特殊节点：x到最近特殊节点的距离 + y到最近特殊节点的距离ans=min(dep[x]-dep[tmp]+dep[y]-dep[tmp],dep2[x]+dep2[y]);else// 如果没有特殊节点，只能走树边ans=dep[x]-dep[tmp]+dep[y]-dep[tmp];cout<<ans<<endl;// 输出结果}// 调试输出每个节点到最近特殊节点的距离// for (int i=1; i<=n; i++)// {// cout << dep2[i] << " ";// }// cout << endl;return0;}【运行结果】
7 2 1 5 7 3 6 2 3 1 5 5 4 1 2 7 4 3 7 4
