%%%
by Integerss @ 2021-07-19 14:03:57
sr时隔inf年竟然在切题
by Integerss @ 2021-07-19 14:05:43
@[Integerss](/user/329840) 看QQ，傻逼
by 一只小可爱吖 @ 2021-07-19 14:07:07
我看nm呢
by Integerss @ 2021-07-19 14:10:57
LCA错了，我用树链剖分写了LCA对了
by yxzy4615 @ 2021-07-19 14:27:56
这边建议用树剖
by Integerss @ 2021-07-19 14:28:01
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,s,root,h[1000010],fa[1000010],de[1000010];
int zs[1000010],ss[1000010],top[1000010];
struct way{
int t,f;
}l[1000010];
void add(int f,int t){
s++;
l[s].f=h[f],l[s].t=t;
h[f]=s;
}
void csh(int x,int f,int deep){
int dz=0;
fa[x]=f;de[x]=deep;ss[x]=1;
for(int i=h[x];i;i=l[i].f){
if(l[i].t!=f){
csh(l[i].t,x,deep+1);
ss[x]+=ss[l[i].t];
if(dz<ss[l[i].t]){
zs[x]=l[i].t;
dz=ss[l[i].t];
}
}
}
}
void pf(int x,int y){
top[x]=y;
if(zs[x]) pf(zs[x],y);
for(int i=h[x];i;i=l[i].f){
if(l[i].t==fa[x]||l[i].t==zs[x]) continue;
pf(l[i].t,l[i].t);
}
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(de[top[x]]>=de[top[y]]) x=fa[top[x]];
else y=fa[top[y]];
}
return de[x]<de[y]?x:y;
}
int main(){
scanf("%d%d",&n,&m);
root=rand()%n;
for(int i=1;i<=n-1;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
csh(root,0,1);
pf(root,root);
for(int i=1;i<=m;i++){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
int x=LCA(a,b),y=LCA(c,d),l=max(de[LCA(a,c)],max(de[LCA(a,d)],max(de[LCA(b,c)],de[LCA(b,d)])));
if(l>=de[x]&&l>=de[y])
cout<<"Y"<<endl;
else
cout<<"N"<<endl;
}
return 0;
}
```
by yxzy4615 @ 2021-07-19 14:28:16