题解：洛谷 P3398 仓鼠找 sugar

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

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

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

【题目来源】

洛谷：P3398 仓鼠找 sugar - 洛谷

【题目描述】

小仓鼠的和他的基（mei）友（zi）sugar 住在地下洞穴中，每个节点的编号为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 #最近公共祖先

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005,M=N*2;intn,Q;// n: 节点数，Q: 查询次数intdep[N];// 节点深度intfa[N][20];// 倍增数组，fa[i][j]表示节点i向上跳2^j步到达的祖先节点queue<int>q;// 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()){intt=q.front();q.pop();for(inti=h[t];i!=-1;i=ne[i]){intj=e[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^0=1步即为父节点tfor(intk=1;k<=19;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(intk=19;k>=0;k--)// 从高位开始尝试跳if(dep[fa[x][k]]>=dep[y])x=fa[x][k];if(x==y)// 如果跳完后x等于y，说明y是x的祖先returnx;// 步骤2：两个节点同时向上跳，跳到公共祖先的下一层for(intk=19;k>=0;k--){if(fa[x][k]!=fa[y][k])// 如果跳2^k步后祖先不同{x=fa[x][k];y=fa[y][k];}}returnfa[x][0];// 返回x的父节点，即x和y的最近公共祖先}// 计算节点a和节点b之间的距离intdist(inta,intb){intp=lca(a,b);// 求最近公共祖先returndep[a]+dep[b]-2*dep[p];// 距离 = a深度 + b深度 - 2*lca深度}intmain(){memset(h,-1,sizeof(h));cin>>n>>Q;for(inti=1;i<n;i++)// 输入n-1条边{intu,v;cin>>u>>v;add(u,v),add(v,u);// 添加无向边}bfs(1);// 从节点1开始预处理深度和倍增数组while(Q--){inta,b,c,d;cin>>a>>b>>c>>d;intab=dist(a,b);// 路径a-b的距离intcd=dist(c,d);// 路径c-d的距离intac=dist(a,c);// 节点a到节点c的距离intbd=dist(b,d);// 节点b到节点d的距离intad=dist(a,d);// 节点a到节点d的距离intbc=dist(b,c);// 节点b到节点c的距离// 判断路径a-b和c-d是否有交点// 条件：路径a-b和c-d有交点当且仅当ab+cd >= max(ac+bd, ad+bc)if(ab+cd>=ac+bd&&ab+cd>=ad+bc)cout<<"Y"<<endl;elsecout<<"N"<<endl;}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