首页 > 分享 > [luogu3398][仓鼠找sugar]

[luogu3398][仓鼠找sugar]

萌宠菠菠乐园
2025-01-06 20:18

luogu3398#

思路:#

假设松鼠a要从a1去a2,松鼠b要从b1去b2，ks表示lca(a1,a2)和lca(b1,b2)中深度较深的那个。那么，若要使得两只松鼠可能相遇，则只要满足lca(a1,b1)，lca(a1,b2),lca(a2,b1),lca(a2,b2)中任意一个的深度深于ks即可。#

代码：#

Copy

#include<cstdio> #include<iostream> using namespace std; const int N=100000+1000,logN=20; int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) { if(c=='-') f=-1; c=getchar();}while(isdigit(c)) {x=x*10+c-'0';c=getchar();}return x*f; } struct node {int v,nxt; }e[N*2]; int head[N],ejs; void add(int u,int v) {e[++ejs].v=v;e[ejs].nxt=head[u];head[u]=ejs; } int lca[N][logN+5],dep[N]; void dfs(int u,int father) {for(int i=1;i<=logN;++i) {lca[u][i]=lca[lca[u][i-1]][i-1];if(!lca[u][i]) break;}for(int i=head[u];i;i=e[i].nxt) {int v=e[i].v;if(v==father) continue;lca[v][0]=u;dep[v]=dep[u]+1;dfs(v,u);} } int LCA(int x,int y) {if(dep[x]>dep[y]) swap(x,y);for(int i=logN;i>=0;--i)if(dep[lca[y][i]]>=dep[x])y=lca[y][i];for(int i=logN;i>=0;--i)if(lca[x][i]!=lca[y][i])x=lca[x][i],y=lca[y][i];if(x!=y) x=lca[x][0];return dep[x]; } int x[3][3]; int main() {int n=read(),q=read();for(int i=1;i<n;++i) {int u=read(),v=read();add(u,v);add(v,u);}dep[0]=-1;dfs(1,0);while(q--) {x[1][1]=read(),x[1][2]=read(),x[0][1]=read(),x[0][2]=read();int ks=max(LCA(x[1][1],x[1][2]),LCA(x[0][1],x[0][2]));int bz=0;for(int i=1;i<=2;++i) {for(int j=1;j<=2;++j) {if(LCA(x[1][i],x[0][j])>=ks) {bz=1;break;}}if(bz==1) break;}if(bz==1) printf("Yn");else printf("Nn");}return 0; }