原题链接：P3398 仓鼠找 sugar
题解里大部分都是用的lca，然而我看不懂那些关于lca的性质是怎么证明出来的。
不过这题可以直接用树链剖分来写，把模板套上去就好了。
题意为查找两条路径是否存在公共点，我们只需要把其中一条路径上的点都赋值为1，然后查询另一条路径上的点的总和，如果总和大于0，说明那条路径经过了这条路径，即这两条路径有公共点。查询完以后要记得将刚才赋值的1减去，防止对后面的查询产生干扰。
会树链剖分的话应该很好理解。
#include<bits/stdc++.h>
#define lp p<<1
#define rp p<<1|1
using namespace std;
const int N=1e5+10;
int n,q;
struct edge{
int v,nxt;
}e[N<<1];
int fir[N],tot=0;
void add_edge(int u,int v){
e[++tot].v=v;
e[tot].nxt=fir[u];
fir[u]=tot;
}
int fa[N],son[N],dep[N],siz[N];
void dfs(int u,int f){
fa[u]=f;
son[u]=0;
dep[u]=dep[f]+1;
siz[u]=1;
for(int i=fir[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==f)continue;
dfs(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v])son[u]=v;
}
}
int dfn[N],id[N],top[N],times=0;
void hld(int u,int topf){
dfn[u]=++times;
id[dfn[u]]=u;
top[u]=topf;
if(!son[u])return;
hld(son[u],topf);
for(int i=fir[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa[u]||v==son[u])continue;
hld(v,v);
}
}
namespace Segment_Tree{
struct node{
int s,t,sum,tag;
}tree[N<<2];
void maintain(int p){
tree[p].sum=tree[lp].sum+tree[rp].sum;
}
void build(int l,int r,int p){
tree[p].s=l;
tree[p].t=r;
tree[p].tag=0;
if(l==r){
tree[p].sum=0;
return;
}
int mid=l+r>>1;
build(l,mid,lp);
build(mid+1,r,rp);
maintain(p);
}
void pushdown(int p){
if(tree[p].tag){
tree[lp].sum+=tree[p].tag*(tree[lp].t-tree[lp].s+1);
tree[rp].sum+=tree[p].tag*(tree[rp].t-tree[rp].s+1);
tree[lp].tag+=tree[p].tag;
tree[rp].tag+=tree[p].tag;
tree[p].tag=0;
}
}
void update(int l,int r,int c,int p){
if(tree[p].s>=l&&tree[p].t<=r){
tree[p].sum+=(tree[p].t-tree[p].s+1)*c;
tree[p].tag+=c;
return;
}
pushdown(p);
int mid=tree[p].s+tree[p].t>>1;
if(l<=mid)update(l,r,c,lp);
if(r>mid)update(l,r,c,rp);
maintain(p);
}
int ask(int l,int r,int p){
if(tree[p].s>=l&&tree[p].t<=r)return tree[p].sum;
pushdown(p);
int mid=tree[p].s+tree[p].t>>1,ans=0;
if(l<=mid)ans+=ask(l,r,lp);
if(r>mid)ans+=ask(l,r,rp);
return ans;
}
}
using namespace Segment_Tree;
void add_chain(int u,int v,int w){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
update(dfn[top[u]],dfn[u],w,1);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
update(dfn[v],dfn[u],w,1);
}
int ask_chain(int u,int v){
int ans=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
ans+=ask(dfn[top[u]],dfn[u],1);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
ans+=ask(dfn[v],dfn[u],1);
return ans;
}
int main(){
cin>>n>>q;
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
add_edge(u,v);
add_edge(v,u);
}
dfs(1,0);
hld(1,1);
build(1,n,1);
for(int i=1;i<=q;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
add_chain(a,b,1);
if(ask_chain(c,d))puts("Y");
else puts("N");
add_chain(a,b,-1);
}
return 0;
}