analysis

本蒟蒻画了好几个图后发现，若树上两条路径有交集，那么必然的，某一条路径会经过另外一条路径起点和终点的LCA

至于怎么证明，我这个蒟蒻怕也是说不明白了

当我们用无论什么方式得到上面的结论以后，本题的问题就转化为了判断点u是否在以s，t为起点和终点的路径上

这很简单，那就是只要满足u到s的距离加u到t的距离等于s到t的距离，即：

$dis[s][u]+dis[u][t]=dis[s][u]$dis[s][u]+dis[u][t]=dis[s][u]

code

时间复杂度分析:

• dfs:O(n*k) （k->20）
• LCA: O(logn)
• main function:O(q*LCA+dfs)
• program:O(q*logn+n)

博主能力不足，若时间复杂度分析有误，敬请大佬斧正

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define clean(arry,num); memset(arry,num,sizeof(arry));
int n,q,cnt=0;
const int maxn=100000+10;
struct node
{
	node():e(0),nxt(0){}
	node(int e,int nxt):e(e),nxt(nxt){}
	int e;int nxt;
}edge[maxn<<1];
int head[maxn];
int dep[maxn];
int f[maxn][30];
inline int read()
{
	int _ans=0;bool _neg=false;char _r=getchar();
	while(_r>'9'||_r<'0'){if(_r=='-')_neg=true;_r=getchar();}
	while(_r>='0'&&_r<='9'){_ans=_ans*10+_r-'0';_r=getchar();}
	return (_neg)?-_ans:_ans;
}
inline void addl(int u,int v)
{
	edge[cnt]=node(v,head[u]);
	head[u]=cnt++;
}
void dfs(int u,int fa)
{
	f[u][0]=fa;
	for(int i=1;(1<<i)<=dep[u];++i)
	{
		if(f[u][i-1]!=-1)f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int i=head[u];i!=-1;i=edge[i].nxt)
	{
		int v=edge[i].e;
		if(v==fa)continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
}
int LCA(int u,int v)
{
	if(u==v)return u;
	if(dep[u]<dep[v]){int t=u;u=v;v=t;}
	for(int i=20;i>=0;--i)
	{
		if(f[u][i]!=-1&&dep[f[u][i]]>=dep[v])u=f[u][i];
	}
	if(u==v)return v;
	for(int i=20;i>=0;--i)
	{
		if(f[u][i]!=-1&&f[v][i]!=-1&&f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
	}
	return f[v][0];
}
inline int disinLCA(int u,int v)
{
	return dep[u]+dep[v]-2*dep[LCA(u,v)];
}
int main()
{
	#ifndef ONLINE_JUDGE
    freopen("datain.txt","r",stdin);
    #endif
    clean(head,-1);
    clean(dep,0);
    clean(f,-1);
    n=read(),q=read();
    loop(i,1,n-1)
	{
		int u,v;
		u=read(),v=read();
		addl(u,v);
		addl(v,u);
	}
	dfs(1,-1);
	loop(i,1,q)
	{
		int a1,b1,a2,b2;
		a1=read();b1=read();
		a2=read();b2=read();
		int lca1=LCA(a1,b1);
		int lca2=LCA(a2,b2);
		if(dep[lca1]<=dep[lca2])//2可能在1路径上  
		{
			if(disinLCA(a1,lca2)+disinLCA(lca2,b1)==disinLCA(a1,b1))
				printf("Y\n");
			else printf("N\n");
		}
		else//1可能在2路径上
		{
			if(disinLCA(lca1,a2)+disinLCA(lca1,b2)==disinLCA(a2,b2))
				printf("Y\n");
			else printf("N\n");
		}
	return 0;
}