题目链接：https://www.luogu.org/problem/P3398
给出a，b，c，d，问a到b的路径和c到d的路径是否有交点。
这里有一个规律（看题解才知道的）就是如果两条路径有交点，那么LCA（a，b）在c到d的路径上或者LCA（c，d）在a到b的路径上，所以我们先求出ab=LCA（a，b），cd=LCA（c，d），判断cd是否在a到b的路径上，只要满足dis（cd，a）+dis（cd，b）==dis（a，b）就行了，也就是cd到a的距离加上cd到b的距离等于a到b的距离，注意这里是距离，用树链剖分的话要用点来代替边，可能有其他做法也不一定。
代码：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 200005 struct node{ int v,next; }edge[maxn]; int a,b,c,d; int n,m,k,t,ID,cnt; int head[maxn],dep[maxn],top[maxn],son[maxn],tot[maxn],fa[maxn],L[maxn]; struct Tree{ int sum; }tree[maxn<<2]; void init(){ memset(head,-1,sizeof(head)); cnt=ID=0; memset(top,0,sizeof(top)); memset(son,0,sizeof(son)); } void add(int u,int v){ edge[++cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt; } void dfs(int u,int pre,int depth){ fa[u]=pre; tot[u]=1; int mx=-INF; dep[u]=depth; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==pre) continue; dfs(v,u,depth+1); tot[u]+=tot[v]; if(tot[v]>mx){ mx=tot[v]; son[u]=v; } } } void dfs2(int u,int pre){ top[u]=pre; L[u]=++ID; if(son[u]==0) return; else dfs2(son[u],pre); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(top[v]==0) dfs2(v,v); } } void update(int k){ tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; } void build(int l,int r,int k){ if(l==r){ tree[k].sum=1; return; } int mid=(l+r)/2; build(l,mid,k<<1); build(mid+1,r,k<<1|1); update(k); } int LCA(int x,int y){//LCA求最近公共祖先 while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); return x; } int ask(int l,int r,int k,int left,int right){//线段树求区间和 if(left>right) return 0; if(l>=left&&r<=right){ return tree[k].sum; } int mid=(l+r)/2; int ans=0; if(left<=mid) ans+=ask(l,mid,k<<1,left,right); if(mid<right) ans+=ask(mid+1,r,k<<1|1,left,right); return ans; } int dis(int x,int y){//求x到y的距离 if(x==y) return 0; int ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=ask(1,ID,1,L[top[x]],L[x]); x=fa[top[x]]; } if(L[x]>L[y]) swap(x,y); ans+=ask(1,ID,1,L[x]+1,L[y]);//点代替边 ，所以编号要加1(树边两端深度更大的那个点) return ans; } int main() { scanf("%d%d",&n,&m); init(); int u,v; for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1,1,1); dfs2(1,1); build(1,ID,1); while(m--){ scanf("%d%d%d%d",&a,&b,&c,&d); int ab=LCA(a,b); int cd=LCA(c,d); if(dis(ab,c)+dis(ab,d)==dis(c,d)||dis(cd,a)+dis(cd,b)==dis(a,b)) printf("Y "); else printf("N "); } return 0; }