ハムスター

テーマはハムスターと彼の基(mei)友(zi)sugarが地下洞窟に住んでいることを記述し、各ノードの番号は1~nである.地下洞窟は木の構造だ.この日、ハムスターは彼の寝室(a)からレストラン(b)まで、彼の親友は同時に彼の寝室(c)から図書館(d)まで行くつもりだった.彼らは最短ルートを歩きます.今ハムスターは、どこかで、彼の親友に会える可能性があるかどうか知りたいと思っています.
ハムスターはそんなに弱くて、また毎日zzqおじいさんに虐げられて、早く助けに来てください!
フォーマットの最初の行の2つの正の整数nとqを入力し、このツリーノードの個数とクエリの個数を表します.
次にn−1行、各行の2つの正の整数uおよびvは、ノードuからノードvの間にエッジがあることを示す.
次にq行は、行ごとに4つの正の整数a,b,c,dがノード番号、すなわち1回のクエリを表し、その意味は上述の通りである.
出力フォーマットは各質問に対して、共通点があれば、大文字「Y」を出力します.そうでなければ「N」を出力します.
入出力サンプル入力#1コピー5 5 2 5 4 2 1 3 1 4 4 4 1 5 1 2 2 4 4 1 3 3 1 5 5 1 4出力#1コピーYNY Y Y説明/提示本題時限1 s、メモリ制限128 M、新評価機速度がNOIP評価機速度に近いため、定数の問題による影響に注意してください.
20%のデータn<=200,q<=200
40%のデータn<=2000,q<=2000
70%のデータn<=50000,q<=50000
100%のデータn<=10000000,q<=10000000
LCAツリー上のパス交差とツリー上の2点間の距離を解く
木の上でどうやってパスを求めますか?(これが題意の求めである),単純な絵図から分かるように,ツリー上の2つの経路が交差する場合,この2つの経路を(a,b)と(c,d),x=lca(a,b),y=lca(c,d)とすると,必ずxが(c,d)経路上,あるいはyが(a,b)経路上にある.
どのようにして1つの点がある経路にあるかどうかを求めますか?実は簡単です.この点からパスの2つの端点までの距離がパスの長さに等しい場合は、このパスにあります.
そしてプログラムの実行速度を速めるためにlog 2(i)+1の値を前処理した.

#pragma GCC optimize(2)
#include
//#define int long long
using namespace std;
const int N=1e5+10;
int n,q,h[N],f[N][30],lg[N],d[N];
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int fa){
	h[x]=h[fa]+1;	f[x][0]=fa;
	for(int i=1;(1<<i)<=h[x];i++)	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nex[i]){
		if(to[i]!=fa)	d[to[i]]=d[x]+1,dfs(to[i],x);
	}
}
inline int lca(int x,int y){
	if(h[x]<h[y])	swap(x,y);
	while(h[x]>h[y])	x=f[x][lg[h[x]-h[y]]-1];
	if(x==y)	return x;
	for(int i=lg[h[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline int dis(int a,int b){
	return d[a]+d[b]-2*d[lca(a,b)];
}
signed main(){
	scanf("%d %d",&n,&q);
	for(int i=1;i<n;i++){
		int a,b;	scanf("%d %d",&a,&b);	add(a,b);	add(b,a);
	}
	for(int i=1;i<=n;i++)	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(1,0);
	while(q--){
		int a,b,c,d;	scanf("%d %d %d %d",&a,&b,&c,&d);
		int x=lca(a,b);	int y=lca(c,d);
		if(dis(c,d)==dis(x,c)+dis(x,d)||dis(a,b)==dis(y,a)+dis(y,b))	puts("Y");
		else	puts("N");
	}
	return 0;
}