题解 P3398 【仓鼠找sugar】

[题目传送门](https://www.luogu.org/problem/P3398) 题目要求两个点之间的路径和另外两个点之间的路径有没有公共点，我们可以先将前两个点之间的路径都打上标记，再查询后两个点之间的路径上是否存在标记即可，每组查询完成后记得清空一下标记。用树链剖分维护，复杂度$O(Nlog^2N)$。 代码： ``` cpp #include<bits/stdc++.h> using namespace std; #define N 100001 inline int read(){int x=0;char c=getchar();while(c<'0' || c>'9')c=getchar();while(c>='0' && c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=getchar();return x;}//快读 int n,q,head[N],cnt1,cnt2,id[N],fa[N],dep[N],top[N],siz[N],son[N]; struct sb2//链式前向星存图 { int a,b; }e[N<<1]; struct sb { int s,la; }tre[N<<2]; inline void add(const int &a,const int &b){e[++cnt1].a=head[a],e[cnt1].b=b,head[a]=cnt1;} inline void dfs1(const int &x,const int &y)//树剖模板 { fa[x]=y; dep[x]=dep[y]+1; siz[x]=1; for(register int i=head[x];i;i=e[i].a) { if(e[i].b==y)continue; dfs1(e[i].b,x); siz[x]+=siz[e[i].b]; if(siz[e[i].b]>siz[son[x]])son[x]=e[i].b; } } inline void dfs2(const int &x,const int &y) { top[x]=y; id[x]=++cnt2; if(!son[x])return; dfs2(son[x],y); for(register int i=head[x];i;i=e[i].a) { if(e[i].b==son[x] || e[i].b==fa[x])continue; dfs2(e[i].b,e[i].b); } } inline void pushdown(int p)//线段树模板 { if(tre[p].la==1) { tre[p<<1].s=tre[p<<1].la=tre[p<<1|1].s=tre[p<<1|1].la=1;tre[p].la=0; } else if(tre[p].la==-1) { tre[p<<1].s=tre[p<<1|1].s=0,tre[p<<1].la=tre[p<<1|1].la=-1;tre[p].la=0; } } inline void add(int p,int l,int r,int a1,int a2,int a3) { if(a1<=l && r<=a2)if(a3==1){tre[p].s=tre[p].la=1;return;}else{tre[p].s=0,tre[p].la=-1;return;} pushdown(p); int mid=l+r>>1; if(mid>=a1)add(p<<1,l,mid,a1,a2,a3); if(mid<a2)add(p<<1|1,mid+1,r,a1,a2,a3); tre[p].s=tre[p<<1].s|tre[p<<1|1].s; } inline int query(int p,int l,int r,int a1,int a2)// { if(a1<=l && r<=a2)return tre[p].s; pushdown(p); int mid=l+r>>1,ans=0; if(mid>=a1)ans=ans || query(p<<1,l,mid,a1,a2); if(mid<a2)ans=ans || query(p<<1|1,mid+1,r,a1,a2); return ans; } signed main() { n=read(),q=read(); for(register int i=1,a,b;i<n;i++)a=read(),b=read(),add(a,b),add(b,a); dfs1(1,0); dfs2(1,1); while(q--) { int x=read(),y=read(); bool bb=0; while(top[x]!=top[y])//打标机 { if(dep[top[x]]<dep[top[y]])swap(x,y); add(1,1,n,id[top[x]],id[x],1); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); add(1,1,n,id[x],id[y],1); x=read(),y=read(); while(top[x]!=top[y])//查询标记 { if(dep[top[x]]<dep[top[y]])swap(x,y); bb=bb || query(1,1,n,id[top[x]],id[x]); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); bb=bb || query(1,1,n,id[x],id[y]); if(bb)putchar('Y');else putchar('N'); putchar('\n'); add(1,1,n,1,n,0);//查询后记得清空标记 } } ```