首页 > 分享 > 仓鼠找sugar

仓鼠找sugar

萌宠菠菠乐园
2025-01-06 21:52

题目传送门

参考 whm" role="presentation">whm 大佬的博客这儿

代码不难，难在思路上。

令 X=lca(a,b)Y=lca(c,d)" role="presentation">X=lca(a,b)Y=lca(c,d)
仓鼠 （cs）" role="presentation">（cs）的路径可以分为从a到X，和从X到b两部分。基友 （jy）" role="presentation">（jy）路径也可以分为从c到Y，和从Y到d两部分。
如果仓鼠和基友相遇的话，可以分为四种情况（向上走或向下走）。
相遇时状态：

cs" role="presentation">cs 从a到X， jy" role="presentation">jy 从c到Y

满足条件的话：则 A=depth[lca(a,c)]>=max(depth[X],depth[Y])" role="presentation">A=depth[lca(a,c)]>=max(depth[X],depth[Y])

原因：每个点向上的路径是唯一的，深度越浅的点越靠上。

cs" role="presentation">cs 从X到b ，jy" role="presentation">jy 从c到Y

满足条件的话：则 B=depth[lca(b,c)]>=max(depth[X],depth[Y])" role="presentation">B=depth[lca(b,c)]>=max(depth[X],depth[Y])

cs" role="presentation">cs 从a到X， jy" role="presentation">jy 从Y到d

满足条件的话：则 C=depth[lca(a,d)]>=max(depth[X],depth[Y])" role="presentation">C=depth[lca(a,d)]>=max(depth[X],depth[Y])

cs" role="presentation">cs 从X到b， jy" role="presentation">jy 从Y到d

满足条件的话：则 D=depth[lca(b,d)]>=max(depth[X],depth[Y])" role="presentation">D=depth[lca(b,d)]>=max(depth[X],depth[Y])

以上四个条件，满足一个即可。所以只需满足 max(mxa(A,B),max(C,D))>=mxa(depth[X],depth[Y])" role="presentation">max(mxa(A,B),max(C,D))>=mxa(depth[X],depth[Y]) 。

所以，六次LCA+比较大小

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N = 500005; int n,q,head[N],tot,fa[N][33]; int dep[N]; struct edge{int node,next; }e[N<<1]; inline int read() {int ans=0,w=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') { w=-1; c=getchar(); }while(c>='0'&&c<='9'){ ans=ans*10+c-'0'; c=getchar();}return ans*w; } inline void add(int x,int y) {e[++tot].node=y;e[tot].next=head[x];head[x]=tot; } void dfs(int u,int f) {dep[u]=dep[f]+1;fa[u][0]=f;for(int i=head[u];i;i=e[i].next){int v=e[i].node;if(v==f) continue;dfs(v,u);} } void work() {for(int i=1;i<=32;i++) for(int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1]; } int lca(int x,int y) {if(dep[x]<dep[y]) swap(x,y);for(int i=32;i>=0;i--)if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];if(x==y) return x;for(int i=32;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];return fa[x][0]; } int main() {n=read(); q=read(); //int s=read();int x,y,a,b,c,d;for(int i=1;i<n;i++){x=read(); y=read();add(x,y); add(y,x);}dfs(1,0); work(); /*for(int i=1;i<=q;i++){a=read(); b=read();printf("%dn",lca(a,b));}*/for(int i=1;i<=q;i++){a=read(); b=read();c=read(); d=read();int X=lca(a,b),Y=lca(c,d);X=max(dep[X],dep[Y]);int A=lca(a,c),B=lca(a,d),C=lca(b,c),D=lca(b,d);A=max(max(dep[A],dep[B]),max(dep[C],dep[D]));if(A>=X) printf("Yn");else printf("Nn"); } return 0; }

竟然因为lcaWA了两次……