题意简述
给定一个\(N\)个节点的树形结构。接下来有\(q\)次询问，每次询问给定\(4\)个节点\(a,b,c,d\)，请计算\(a\)到\(b\)的简单路径和\(c\)到\(d\)的简单路径是否有相交的节点。对于每个询问，输出Y/N表示答案。
解题思路 & Code
通过手玩样例可以发现，\(a\sim b\)与\(c\sim d\)有相交节点，当且仅当\(lca(a,b)\)在\(c\sim d\)上，或者\(lca(c,d)\)在\(a\sim b\)上。
那么我们怎么判断一个点在一条路径上呢？
我们设路径端点为\(a,b\)，要判断节点\(c\)是否在\(a\sim b\)上。
通过寻找规律，我们可以把“\(c\)在\(a\sim b\)上”归纳为下面\(2\)种情况：
- \(c\)在\(a\sim lca(a,b)\)上：\(lca(a,c)=c\)且\(lca(a,b)=lca(b,c)\)。
- \(c\)在\(b\sim lca(a,b)\)上：\(lca(b,c)=c\)且\(lca(a,b)=lca(a,c)\)。
只要满足其一，就说明\(c\)在\(a\sim b\)上。我们把判断的过程写成函数onpath(a,b,c)，对于每次询问，如果onpath(a,b,lca(c,d))||onpath(c,d,lca(a,b))，则输出Y，否则输出N。
就酱。
时间复杂度\(O((N+q)\log N)\)。
点击查看代码
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int dep[N],fa[N][20];
int n,q;
vector<int> G[N];
void dfs(int u,int father){
dep[u]=dep[father]+1;
fa[u][0]=father;
for(int i=1;i<20;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i:G[u])
if(i!=father) dfs(i,u);
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--)
if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];
if(u==v) return v;
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
bool onpath(int a,int b,int c){
int ab=lca(a,b),bc=lca(b,c),ac=lca(a,c);
return (ac==c&&ab==bc)||(bc==c&&ab==ac);
}
int main(){
cin>>n>>q;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
while(q--){
int a,b,c,d;
cin>>a>>b>>c>>d;
if(onpath(a,b,lca(c,d))||onpath(c,d,lca(a,b)))
cout<<"Y\n";
else cout<<"N\n";
}
return 0;
}