首页 > 分享 > [ Luogu 3398 ] 仓鼠找sugar

[ Luogu 3398 ] 仓鼠找sugar

萌宠菠菠乐园
2024-11-02 12:08

Description" role="presentation">Description

给出一棵N" role="presentation">N个节点的树，K" role="presentation">K次询问从Ai" role="presentation">Ai到Bi" role="presentation">Bi的最短路径，与从Ci" role="presentation">Ci到Di" role="presentation">Di的最短路径是否有交。

N,K∈[1,105]" role="presentation">N,K∈[1,105]

Solution" role="presentation">Solution

倍增Lca" role="presentation">Lca板子。注意到树形结构不会出现环，所以如果有交必然有一个Lca" role="presentation">Lca在另一个Lca" role="presentation">Lca到产生它的两个节点的路径之一上。用画图形象化的表示：

图上已经标出了四种(" role="presentation">(八种)" role="presentation">)可能的情况。

然后就判一波Lca" role="presentation">Lca之间的关系就好，假设要判断点m" role="presentation">m是否在从l" role="presentation">l到r" role="presentation">r的路径上，其中r" role="presentation">r是l" role="presentation">l的祖先，则成立条件就是Lca(l,m)=m" role="presentation">Lca(l,m)=m并且deepm>deepr" role="presentation">deepm>deepr。

Code" role="presentation">Code

#include<cmath> #include<queue> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 100010 #define R register #define gc getchar using namespace std; inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x; } int n,m,t,tot,d[N],hd[N],f[N][20]; struct edge{int to,nxt;}e[N<<1]; inline void add(int u,int v){ e[++tot].to=v; e[tot].nxt=hd[u]; hd[u]=tot; } queue<int> q; inline void bfs(){ q.push(1); d[1]=1; while(!q.empty()){ int u=q.front(); q.pop(); for(R int i=hd[u],v;i;i=e[i].nxt) if(!d[v=e[i].to]){ d[v]=d[u]+1; f[v][0]=u; for(R int j=1;j<=t;++j) f[v][j]=f[f[v][j-1]][j-1]; q.push(v); } } } inline int lca(int u,int v){ if(d[u]>d[v]) u^=v^=u^=v; for(R int i=t;~i;--i) if(d[f[v][i]]>=d[u]) v=f[v][i]; if(u==v) return u; for(R int i=t;~i;--i) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i]; return f[u][0]; } inline bool valid(int m,int l,int r){return (lca(m,l)==m&&d[m]>=d[r]);} inline bool check(int a,int b,int c,int d){ int l1=lca(a,b),l2=lca(c,d); return (valid(l2,a,l1)||valid(l2,b,l1)||valid(l1,c,l2)||valid(l1,d,l2)); } int main(){ t=log2(n=rd())+1; m=rd(); for(R int i=1,u,v;i<n;++i){ u=rd(); v=rd(); add(u,v); add(v,u); } bfs(); for(R int i=1,a,b,c,d;i<=m;++i){ a=rd(); b=rd(); c=rd(); d=rd(); puts(check(a,b,c,d)?"Y":"N"); } return 0; }