时间限制：1s
内存限制：256MB
【问题描述】
已知我国有 n 座城市，这些城市通过 n-1 条高铁相连。且任意两个城市联通。
小 A 想从 x1 号城市出发，到 y1 号城市，小 B 想从 x2 号城市出发，到 y2 号
城市，问他们是否可能在路途中相遇（出现在同一城市）
你需要回答 m 次这样的问题。
【输入】
输入文件名为 railway.in。
第一行一个数 T(<=10)，表示数据组数
对于每一组数据：
第一行两个数 n,m（1<=n,m<=100,000）
第 2～n 行，每行两个数 x,y 表示有一条铁路连接城市 x 和 y
接下来 m 行每行四个数，分别表示 x1,y1,x2,y2，表示一次询问
【输出】
输出文件名为 railway.out。
对于每次询问输出 YES 或 NO
【输入输出样例】
railway.in railway.out
1
4 2
1 2
2 3
3 4
1 2 3 4
1 4 2 3
NO
YES
【数据说明】
对于 30%的数据，n,m<=100
对于 60%的数据，n,m<=1000
对于 100%的数据，n,m<=100,000
实际题意就是判断树上两条路径是否有交汇点。
路径a-b的LCA为e
路径c-d的LCA为f
如果有交汇点，那么e点在路径c-d上或f点在路径a-b上。
以点e在路径c-d上为例，那么e点在c-f上或在d-f上。
这样问题就变成了点z点是否在路径x-y上，其中y点为x的祖先。
那么只需要用深搜出现的次序就可以判断。
既l[x]<=l[z]<=l[y]且r[y]<=r[z]<=r[x]!
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int t,n,m;
struct edge
{
int u,v,nxt;
}e[maxn<<1];
int head[maxn],js;
void addage(int u,int v)
{
e[++js].u=u;e[js].v=v;
e[js].nxt=head[u];head[u]=js;
}
int lg[maxn];
int l[maxn],r[maxn],f[maxn][20],dep[maxn],cnt;
void init()
{
js=0;cnt=0;
memset(e,0,sizeof e);
memset(head,0,sizeof head);
memset(l,0,sizeof l);
memset(r,0,sizeof r);
memset(dep,0,sizeof dep);
memset(f,0,sizeof f);
}
void dfs(int u,int fa)
{
l[u]=++cnt;
dep[u]=dep[fa]+1;
f[u][0]=fa;
for(int i=1;f[u][i-1]&&i<20;++i)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
}
r[u]=++cnt;
}
int lca(int u,int v)
{
if(dep[v]>dep[u])swap(u,v);
while(dep[u]>dep[v])u=f[u][lg[dep[u]-dep[v]]];
if(u==v)return u;
for(int i=19;i>=0;--i)
{
if(f[u][i]!=f[v][i])
{
u=f[u][i];v=f[v][i];
}
}
return f[u][0];
}
bool zai(int a,int b,int c)
{
return l[b]<=l[a]&&l[a]<=l[c]&&r[c]<=r[a]&&r[a]<=r[b];
}
int main()
{
freopen("railway.in","r",stdin);
freopen("railway.out","w",stdout);
scanf("%d",&t);
lg[0]=-1;
for(int i=1;i<=100000;++i)lg[i]=lg[i/2]+1;
while(t--)
{
init();
scanf("%d%d",&n,&m);
for(int u,v,i=1;i<n;++i)
{
scanf("%d%d",&u,&v);
addage(u,v);
addage(v,u);
}
dfs(1,0);
for(int a,b,c,d,e,f,i=0;i<m;++i)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
e=lca(a,b);
f=lca(c,d);
if(zai(f,e,a)||zai(f,e,b)||zai(e,f,c)||zai(e,f,d))puts("YES");
else puts("NO");
}
}
return 0;
}