这还是一道比较好的树剖题（去你的树剖，LCA即可）
这里主要讲两种思路，其实都是很基本也很经典的
1 树链剖分
还是先讲一下这种算法吧，虽然写起来很烦（不过感觉写多了就习惯了，而且还有一种莫名的快感），但是思路好想啊！
我们可以把\(a \to b\)的路径上的点权都加上1，然后把\(c \to d\)的路径上的点权都加上1
然后就很简单了，就是查询这棵树中有没有点权为2的点。
熟悉线段树的就可以秒了，我们只需要建一棵维护最大值的segtree即可
CODE
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
struct edge
{
int to,next;
}e[N<<1];
struct segtree
{
int x,add;
}tree[N<<2];
int n,q,a,b,c,d,cnt,tot,rt=1,head[N],dep[N],father[N],top[N],id[N],size[N],son[N];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void add(int x,int y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline void swap(int &a,int &b)
{
int t=a; a=b; b=t;
}
inline int max(int a,int b)
{
return a>b?a:b;
}
inline void up(int rt)
{
tree[rt].x=max(tree[rt<<1].x,tree[rt<<1|1].x);
}
inline void down(int rt)
{
if (tree[rt].add)
{
tree[rt<<1].add+=tree[rt].add; tree[rt<<1|1].add+=tree[rt].add;
tree[rt<<1].x+=tree[rt].add; tree[rt<<1|1].x+=tree[rt].add;
tree[rt].add=0;
}
}
inline void modify(int rt,int l,int r,int beg,int end,int k)
{
if (l>=beg&&r<=end)
{
tree[rt].x+=k; tree[rt].add+=k;
return;
}
int mid=l+r>>1; down(rt);
if (beg<=mid) modify(rt<<1,l,mid,beg,end,k);
if (end>mid) modify(rt<<1|1,mid+1,r,beg,end,k);
up(rt);
}
inline void DFS1(int now,int fa,int d)
{
dep[now]=d; father[now]=fa; size[now]=1; int res=-1;
for (register int i=head[now];i!=-1;i=e[i].next)
if (e[i].to!=fa)
{
DFS1(e[i].to,now,d+1);
size[now]+=size[e[i].to];
if (size[e[i].to]>res) res=size[e[i].to],son[now]=e[i].to;
}
}
inline void DFS2(int now,int topf)
{
top[now]=topf; id[now]=++tot;
if (!son[now]) return;
DFS2(son[now],topf);
for (register int i=head[now];i!=-1;i=e[i].next)
if (e[i].to!=father[now]&&e[i].to!=son[now]) DFS2(e[i].to,e[i].to);
}
inline void change(int x,int y,int z)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
modify(1,1,n,id[top[x]],id[x],z); x=father[top[x]];
}
if (dep[x]<dep[y]) swap(x,y);
modify(1,1,n,id[y],id[x],z);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
memset(e,-1,sizeof(e));
memset(head,-1,sizeof(head));
register int i; read(n); read(q);
for (i=1;i<n;++i)
read(a),read(b),add(a,b),add(b,a);
DFS1(rt,-1,0); DFS2(rt,rt);
while (q--)
{
read(a); read(b); read(c); read(d);
change(a,b,1); change(c,d,1);
puts(tree[1].x>=2?"Y":"N");
change(a,b,-1); change(c,d,-1);
}
return 0;
}
2 LCA
因为这道题本身还是LCA为正解的，所以我们搞一下。
我们考虑什么时候树上的两条链会有交点。
我们很轻易地通过大量的证明画图归纳得到：如果两条路径相交，那么一定有一条路径的LCA在另一条路径上
然后这里我们判断一个节点\(x\)，是否在路径\(u \to v\)上需要满足：
- \(dep_x>=dep_{LCA(u,v)}\)
- \(LCA(u,x)=x\ or\ LCA(v,x)=x\)
这个的话还是多思考，多总结一下就好的东西
由于LCA多年未写，Tarjan&&倍增全忘了，只会一个DFS序+RMQ的了
其实个人喜欢DFS序的那种，毕竟预处理\(O(nlogn)\)，查询只要\(O(1)\)
CODE
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=100005,P=20;
struct edge
{
int to,next;
}e[N<<1];
struct RMQ
{
int x,num;
}f[N<<1][P];
int n,q,a,b,c,d,cnt,tot,rt=1,head[N],fir[N],dep[N];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void add(int x,int y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline void swap(int &a,int &b)
{
int t=a; a=b; b=t;
}
inline void DFS(int now,int fa,int d)
{
dep[now]=f[++tot][0].x=d; fir[now]=tot; f[tot][0].num=now;
for (register int i=head[now];i!=-1;i=e[i].next)
if (e[i].to!=fa) DFS(e[i].to,now,d+1),f[++tot][0].x=d,f[tot][0].num=now;
}
inline void RMQ_init(void)
{
for (register int j=1;j<P;++j)
for (register int i=1;i+(1<<j)-1<=tot;++i)
f[i][j]=f[i][j-1].x<f[i+(1<<j-1)][j-1].x?f[i][j-1]:f[i+(1<<j-1)][j-1];
}
inline int LCA(int x,int y)
{
x=fir[x]; y=fir[y]; if (x>y) swap(x,y);
int k=(int)log2(y-x+1);
return f[x][k].x<f[y-(1<<k)+1][k].x?f[x][k].num:f[y-(1<<k)+1][k].num;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(n); read(q);
memset(e,-1,sizeof(e));
memset(head,-1,sizeof(head));
for (i=1;i<n;++i)
read(a),read(b),add(a,b),add(b,a);
DFS(rt,-1,0); RMQ_init();
while (q--)
{
read(a); read(b); read(c); read(d);
int fa1=LCA(a,b),fa2=LCA(c,d);
if (dep[fa1]>dep[c]&&dep[fa1]>dep[d]) { puts("N"); continue; }
if (dep[fa2]>dep[a]&&dep[fa2]>dep[b]) { puts("N"); continue; }
if (dep[fa1]>=dep[fa2])
{
if (!(LCA(fa1,c)^fa1)||!(LCA(fa1,d)^fa1)) { puts("Y"); continue; }
} else if (!(LCA(fa2,a)^fa2)||!(LCA(fa2,b)^fa2)) { puts("Y"); continue; }
puts("N");
}
return 0;
}