本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-11 17:52:09

思路

设一条路径为 $(a,b)$，另一条为 $(c,d)$，两条路径如果相交，那么有 $lca(a,b)$ 在 $(c,d)$ 上或 $lca(c,d)$ 在 $(a,b)$上，这个东西画一下图就能理解，但是我不知道怎么证明

可以这么理解：
首先已知对于任意两个点 $x,y$，$lca(x,y)$ 一定在 $x$ 到 $y$ 的路径上。
先确定了一条路径 $(a,b)$ 和路径外的一点 $c$，还有一个点 $d$ 未知。要使 $(a,b)$ 与 $(c,d)$ 相交，就要使 $lca(c,d)$ 成为路径 $(a,b)$ 上的一点。

那么如何判断一个点是否在某条路径上呢？
设判断 $a$ 是否在 $(c,d)$ 上，如果 $dis_{c,a} + dis_{a,d} = dis_{c,d}$，那么 $a$ 就在 $(c,d)$ 上
另外显然，$dis_{a,b} = dep_a + dep_b - 2 \cdot dep_{lca(a,b)}$（$dep$ 是节点的深度）

代码

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=100005;
	int n,q;
	int head[maxn<<1];
	struct EDGE
	{
		int to,nxt;
	}edge[maxn<<1];
	int cnt;
	inline void add(int u,int to)
	{
		edge[++cnt].to=to;
		edge[cnt].nxt=head[u];
		head[u]=cnt;
	}
	int dep[maxn];
	int fa[18][maxn];
	void dfs(int u,int _fa)
	{
		dep[u]=dep[_fa]+1;
		fa[0][u]=_fa;
		for(int i=1;i<=17;i++)
		{
			fa[i][u]=fa[i-1][fa[i-1][u]];
		}
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==_fa)continue;
			dfs(to,u);
		}
	}
	inline int lca(int a,int b)
	{
		if(dep[a]<dep[b])swap(a,b);
		for(int i=17;i>=0;i--)
		{
			if(dep[fa[i][a]]>=dep[b])
			{
				a=fa[i][a];
			}
		}
		if(a==b)return a;
		for(int i=17;i>=0;i--)
		{
			if(fa[i][a]!=fa[i][b])
			{
				a=fa[i][a];
				b=fa[i][b];
			}
		}
		return fa[0][a];
	}
	inline int dis(int a,int b)
	{\/\/计算 a,b 两点的距离 
		int _lca=lca(a,b);
		return dep[a]+dep[b]-2*dep[_lca];
	}
	inline bool check(int a,int b,int c)
	{\/\/判断 c 是否在 a,b 的链上 
		if(dis(a,c)+dis(c,b)==dis(a,b))
		{
			return 1;
		}
		return 0;
	}
	void main()
	{
		scanf("%d%d",&n,&q);
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v);
			add(v,u);
		}
		dfs(1,0);
		for(int i=1;i<=q;i++)
		{
			int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			int _lca_ab=lca(a,b);
			int _lca_cd=lca(c,d);
			if(check(a,b,_lca_cd)||check(c,d,_lca_ab))
			{
				printf("Y\n");
			}
			else printf("N\n");
		}
	}
}
int main()
{
	Main::main();
	return 0;
}