本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P3398 仓鼠找 sugar - 洛谷【题目描述】小仓鼠的和他的基mei友zisugar 住在地下洞穴中每个节点的编号为1 ∼ n 1\sim n1∼n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室a aa到餐厅b bb而他的基友同时要从他的卧室c cc到图书馆d dd。他们都会走最短路径。现在小仓鼠希望知道有没有可能在某个地方可以碰到他的基友小仓鼠那么弱还要天天被 zzq 大爷虐请你快来救救他吧【输入】第一行两个正整数n nn和q qq表示这棵树节点的个数和询问的个数。接下来n − 1 n-1n−1行每行两个正整数u uu和v vv表示节点u uu到节点v vv之间有一条边。接下来q qq行每行四个正整数a aa、b bb、c cc和d dd表示节点编号也就是一次询问其意义如上。【输出】对于每个询问如果有公共点输出大写字母Y否则输出N。【输入样例】5 5 2 5 4 2 1 3 1 4 5 1 5 1 2 2 1 4 4 1 3 4 3 1 1 5 3 5 1 4【输出样例】Y N Y Y Y【算法标签】#普及plus #最近公共祖先【代码详解】#includebits/stdc.husingnamespacestd;constintN100005,MN*2;intn,Q;// n: 节点数Q: 查询次数intdep[N];// 节点深度intfa[N][20];// 倍增数组fa[i][j]表示节点i向上跳2^j步到达的祖先节点queueintq;// BFS队列inth[N],e[M],ne[M],idx;// 邻接表存储树// 添加无向边voidadd(inta,intb){e[idx]b,ne[idx]h[a],h[a]idx;}// 预处理节点深度和倍增数组voidbfs(introot){memset(dep,0x3f,sizeof(dep));// 初始化深度为无穷大dep[0]0,dep[root]1;// 虚拟0节点深度为0根节点深度为1q.push(root);while(!q.empty()){inttq.front();q.pop();for(intih[t];i!-1;ine[i]){intje[i];// 子节点jif(dep[j]dep[t]1)// 如果j的深度大于t的深度1即j未访问{dep[j]dep[t]1;// 计算j的深度q.push(j);// j入队列fa[j][0]t;// j向上走2^01步即为父节点tfor(intk1;k19;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])// 保证x为深度较大的节点swap(x,y);// 步骤1把节点x向上跳直到与节点y深度相同for(intk19;k0;k--)// 从高位开始尝试跳if(dep[fa[x][k]]dep[y])xfa[x][k];if(xy)// 如果跳完后x等于y说明y是x的祖先returnx;// 步骤2两个节点同时向上跳跳到公共祖先的下一层for(intk19;k0;k--){if(fa[x][k]!fa[y][k])// 如果跳2^k步后祖先不同{xfa[x][k];yfa[y][k];}}returnfa[x][0];// 返回x的父节点即x和y的最近公共祖先}// 计算节点a和节点b之间的距离intdist(inta,intb){intplca(a,b);// 求最近公共祖先returndep[a]dep[b]-2*dep[p];// 距离 a深度 b深度 - 2*lca深度}intmain(){memset(h,-1,sizeof(h));cinnQ;for(inti1;in;i)// 输入n-1条边{intu,v;cinuv;add(u,v),add(v,u);// 添加无向边}bfs(1);// 从节点1开始预处理深度和倍增数组while(Q--){inta,b,c,d;cinabcd;intabdist(a,b);// 路径a-b的距离intcddist(c,d);// 路径c-d的距离intacdist(a,c);// 节点a到节点c的距离intbddist(b,d);// 节点b到节点d的距离intaddist(a,d);// 节点a到节点d的距离intbcdist(b,c);// 节点b到节点c的距离// 判断路径a-b和c-d是否有交点// 条件路径a-b和c-d有交点当且仅当abcd max(acbd, adbc)if(abcdacbdabcdadbc)coutYendl;elsecoutNendl;}return0;}【运行结果】5 5 2 5 4 2 1 3 1 4 5 1 5 1 Y 2 2 1 4 N 4 1 3 4 Y 3 1 1 5 Y 3 5 1 4 Y
题解：洛谷 P3398 仓鼠找 sugar
发布时间：2026/5/22 2:18:21
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P3398 仓鼠找 sugar - 洛谷【题目描述】小仓鼠的和他的基mei友zisugar 住在地下洞穴中每个节点的编号为1 ∼ n 1\sim n1∼n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室a aa到餐厅b bb而他的基友同时要从他的卧室c cc到图书馆d dd。他们都会走最短路径。现在小仓鼠希望知道有没有可能在某个地方可以碰到他的基友小仓鼠那么弱还要天天被 zzq 大爷虐请你快来救救他吧【输入】第一行两个正整数n nn和q qq表示这棵树节点的个数和询问的个数。接下来n − 1 n-1n−1行每行两个正整数u uu和v vv表示节点u uu到节点v vv之间有一条边。接下来q qq行每行四个正整数a aa、b bb、c cc和d dd表示节点编号也就是一次询问其意义如上。【输出】对于每个询问如果有公共点输出大写字母Y否则输出N。【输入样例】5 5 2 5 4 2 1 3 1 4 5 1 5 1 2 2 1 4 4 1 3 4 3 1 1 5 3 5 1 4【输出样例】Y N Y Y Y【算法标签】#普及plus #最近公共祖先【代码详解】#includebits/stdc.husingnamespacestd;constintN100005,MN*2;intn,Q;// n: 节点数Q: 查询次数intdep[N];// 节点深度intfa[N][20];// 倍增数组fa[i][j]表示节点i向上跳2^j步到达的祖先节点queueintq;// BFS队列inth[N],e[M],ne[M],idx;// 邻接表存储树// 添加无向边voidadd(inta,intb){e[idx]b,ne[idx]h[a],h[a]idx;}// 预处理节点深度和倍增数组voidbfs(introot){memset(dep,0x3f,sizeof(dep));// 初始化深度为无穷大dep[0]0,dep[root]1;// 虚拟0节点深度为0根节点深度为1q.push(root);while(!q.empty()){inttq.front();q.pop();for(intih[t];i!-1;ine[i]){intje[i];// 子节点jif(dep[j]dep[t]1)// 如果j的深度大于t的深度1即j未访问{dep[j]dep[t]1;// 计算j的深度q.push(j);// j入队列fa[j][0]t;// j向上走2^01步即为父节点tfor(intk1;k19;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])// 保证x为深度较大的节点swap(x,y);// 步骤1把节点x向上跳直到与节点y深度相同for(intk19;k0;k--)// 从高位开始尝试跳if(dep[fa[x][k]]dep[y])xfa[x][k];if(xy)// 如果跳完后x等于y说明y是x的祖先returnx;// 步骤2两个节点同时向上跳跳到公共祖先的下一层for(intk19;k0;k--){if(fa[x][k]!fa[y][k])// 如果跳2^k步后祖先不同{xfa[x][k];yfa[y][k];}}returnfa[x][0];// 返回x的父节点即x和y的最近公共祖先}// 计算节点a和节点b之间的距离intdist(inta,intb){intplca(a,b);// 求最近公共祖先returndep[a]dep[b]-2*dep[p];// 距离 a深度 b深度 - 2*lca深度}intmain(){memset(h,-1,sizeof(h));cinnQ;for(inti1;in;i)// 输入n-1条边{intu,v;cinuv;add(u,v),add(v,u);// 添加无向边}bfs(1);// 从节点1开始预处理深度和倍增数组while(Q--){inta,b,c,d;cinabcd;intabdist(a,b);// 路径a-b的距离intcddist(c,d);// 路径c-d的距离intacdist(a,c);// 节点a到节点c的距离intbddist(b,d);// 节点b到节点d的距离intaddist(a,d);// 节点a到节点d的距离intbcdist(b,c);// 节点b到节点c的距离// 判断路径a-b和c-d是否有交点// 条件路径a-b和c-d有交点当且仅当abcd max(acbd, adbc)if(abcdacbdabcdadbc)coutYendl;elsecoutNendl;}return0;}【运行结果】5 5 2 5 4 2 1 3 1 4 5 1 5 1 Y 2 2 1 4 N 4 1 3 4 Y 3 1 1 5 Y 3 5 1 4 Y
