传送门
解题思路
很显然，就是在一棵树上，求两条路径有没有交点。
我们可以先分别求出两条路径两段点的LCA，设为rtab和rtcd然后分以下情况讨论：
- 当rtab==rtcd时，一定有交点（就是这个LCA）。
- 当rtab的深度大于c和d的深度或者rtcd的深度大于a和b的深度时，一定没有交点。（因为LCA一定是路径上最浅的点）
- 当rtab的深度大于rtcd时，若有交点，那么rtab一定在c到rtcd的路径上或者在d到rtcd的路径上，求出rtab和c的LCA、rtab和d的LCA，若有一个等于rtab，则有交点。
- 当rtcd的深度大于rtab时，同理。
- 否则就输出“N"。
这时候可能会发现，会不会rtab和rtcd的深度相同这种情况呢？
如果rtab和rtcd深度相同却又不是同一个节点（若是同一个节点在第一种情况里已经判断），显然两条路径不可能有交点。
代码就是先树剖剖一下，然后对于每个询问求上述情况的LCA，判断输出即可。
AC代码
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> using namespace std; const int maxn=100005; int cnt,p[maxn],fa[maxn],deep[maxn],top[maxn],size[maxn],son[maxn]; int n,q; struct node{ int v,next; }e[maxn*2]; void insert(int u,int v){ cnt++; e[cnt].v=v; e[cnt].next=p[u]; p[u]=cnt; } void dfs1(int u,int f,int dep){ int maxsize=0; fa[u]=f; size[u]=1; deep[u]=dep; for(int i=p[u];i!=-1;i=e[i].next){ int v=e[i].v; if(v==fa[u]) continue; dfs1(v,u,dep+1); size[u]+=size[v]; if(size[v]>maxsize){ maxsize=size[v]; son[u]=v; } } } void dfs2(int u,int topp){ top[u]=topp; if(son[u])dfs2(son[u],topp); for(int i=p[u];i!=-1;i=e[i].next){ int v=e[i].v; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } int findrt(int x,int y){ while(top[x]!=top[y]){ if(deep[top[x]]<deep[top[y]]) swap(x,y); x=fa[top[x]]; } return deep[x]>deep[y]?y:x; } int main() { memset(p,-1,sizeof(p)); cin>>n>>q; for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); insert(u,v); insert(v,u); } dfs1(1,-1,1); dfs2(1,1); for(int i=1;i<=q;i++){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); int rtab=findrt(a,b); int rtcd=findrt(c,d); int rtc1=findrt(c,rtab); int rtd1=findrt(d,rtab); int rta2=findrt(a,rtcd); int rtb2=findrt(b,rtcd); if(deep[rtab]>max(deep[c],deep[d])||deep[rtcd]>max(deep[a],deep[b])){ printf("N "); continue; } if(rtab==rtcd||(deep[rtab]>deep[rtcd]&&(rtc1==rtab||rtd1==rtab))||(deep[rtab]<deep[rtcd]&&(rta2==rtcd||rtb2==rtcd)))printf("Y "); else printf("N "); } return 0; }