仓鼠找sugar

洛咕

题意:给定一棵(n(n<=1e5))个节点的树,每次询问两条路径((a,b),(x,y))是否有公共点.

分析:手玩了几种路径,发现((a,b),(x,y))两条路径有公共点,当且仅当(LCA(a,b))在((x,y))上 或者 (LCA(x,y))在((a,b))上.

然后如何判断(LCA(a,b))是否在((x,y))这条路径上?即该点到路径两端点的距离之和等于两端点之间的距离.即

(dis[x]+dis[y]-2*dep[LCA(x,y)]=dep[x]+dep[LCA(a,b)]-2*dep[LCA(x,LCA(a,b))]+dep[y]+dep[LCA(a,b)]-2*dep[LCA(y,LCA(a,b))]).

化简一下上式可得(dep[LCA(a,b)]+dep[LCA(x,y)]=dep[LCA(x,LCA(a,b))]+dep[y,LCA(a,b)]).

判断(LCA(x,y))是否在((a,b))这条路径上?同理可得.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=100005;
int tot,head[N],nxt[N<<1],to[N<<1];
inline void add(int a,int b){nxt[++tot]=head[a];head[a]=tot;to[tot]=b;}
int f[N][25],dep[N];
inline void dfs(int u,int fa){
	for(int j=1;j<=20;++j)f[u][j]=f[f[u][j-1]][j-1];
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fa)continue;
		f[v][0]=u;dep[v]=dep[u]+1;dfs(v,u);
	}
}
inline int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int j=20;j>=0;--j)
		if(dep[f[x][j]]>=dep[y])x=f[x][j];
	if(x==y)return x;
	for(int j=20;j>=0;--j)
		if(f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];
	return f[x][0];
}
int main(){
	int n=read(),q=read();
	for(int i=1;i<n;++i){
		int a=read(),b=read();
		add(a,b);add(b,a);
	}
	dep[1]=1;f[1][0]=1;dfs(1,0);
	while(q--){
		int a=read(),b=read(),x=read(),y=read();
		int lca1=LCA(a,b),lca2=LCA(x,y),lca3=LCA(x,lca1),lca4=LCA(y,lca1),lca5=LCA(a,lca2),lca6=LCA(b,lca2);
		if(dep[lca1]+dep[lca2]==dep[lca3]+dep[lca4]||dep[lca1]+dep[lca2]==dep[lca5]+dep[lca6])puts("Y");
		else puts("N");
	}
    return 0;
}