题目：https://www.luogu.org/problemnew/show/P3398
树链剖分一下，路径就变成线段树上的几个区间；
两条路径相交就是线段树上有区间相交，所以在相应位置打个标记，查询有无标记即可；
一开始是打1的标记，查询后就减去，查询 sum 是否为 0 即可；
然而这样写却全 WA 了...悲痛欲绝去看了 TJ ，模仿了其写法，回头再看发现是忘记写 pushdown ，而且 -1 的地方写成 0 了囧...
改掉就 A 了，这个做法完全没问题嘛！
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=1e5+;
int n,q,hd[maxn],ct,sum[maxn<<],tim,fa[maxn],lzy[maxn<<];
int dep[maxn],dfn[maxn],top[maxn],son[maxn],siz[maxn],id[maxn];
struct N{
int to,nxt;
N(int t=,int n=):to(t),nxt(n) {}
}ed[maxn<<];
void add(int x,int y){ed[++ct]=N(y,hd[x]); hd[x]=ct;}
void dfs(int x,int f)
{
dep[x]=dep[f]+; siz[x]=; fa[x]=f;
for(int i=hd[x],u;i;i=ed[i].nxt)
{
if((u=ed[i].to)==f)continue;
dfs(u,x); siz[x]+=siz[u];
if(siz[u]>siz[son[x]])son[x]=u;
}
}
void dfs2(int x)
{
dfn[x]=++tim; id[tim]=x;//
if(son[x])top[son[x]]=top[x],dfs2(son[x]);
for(int i=hd[x],u;i;i=ed[i].nxt)
{
if((u=ed[i].to)==fa[x]||u==son[x])continue;
top[u]=u; dfs2(u);
}
}
void pushup(int x){sum[x]=sum[x<<]+sum[x<<|];}
void pushdown(int x,int l,int r)
{
if(!lzy[x])return;
int ls=(x<<),rs=(x<<|),mid=((l+r)>>);
lzy[ls]+=lzy[x]; lzy[rs]+=lzy[x];
sum[ls]+=lzy[x]*(mid-l+); sum[rs]+=lzy[x]*(r-mid);
lzy[x]=;
}
void add(int x,int l,int r,int L,int R,int val)
{
if(l>=L&&r<=R){sum[x]+=val*(r-l+); lzy[x]+=val; return;}
pushdown(x,l,r);//
int mid=((l+r)>>);
if(mid>=L)add(x<<,l,mid,L,R,val);
if(mid<R)add(x<<|,mid+,r,L,R,val);
pushup(x);
}
int ask(int x,int l,int r,int L,int R)
{
if(l>=L&&r<=R)return sum[x];
pushdown(x,l,r);//
int ret=,mid=((l+r)>>);
if(mid>=L)ret+=ask(x<<,l,mid,L,R);
if(mid<R)ret+=ask(x<<|,mid+,r,L,R);
return ret;
}
void update(int x,int y,int val)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
add(,,n,dfn[top[x]],dfn[x],val);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
add(,,n,dfn[y],dfn[x],val);
}
bool query(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
if(ask(,,n,dfn[top[x]],dfn[x])) return ;
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
return ask(,,n,dfn[y],dfn[x]);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(,); top[]=; dfs2();
for(int i=,a,b,c,d;i<=q;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
update(a,b,);
if(query(c,d))printf("Y\n");
else printf("N\n");
update(a,b,-);//!0
}
return ;
}
还有 TJ 写法，就是不删除了，打个 int 类型的标记，所以查询 max 即可。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=1e5+;
int n,q,hd[maxn],ct,mx[maxn<<],tim,fa[maxn],lzy[maxn<<],tot;
int dep[maxn],dfn[maxn],top[maxn],son[maxn],siz[maxn],id[maxn];
struct N{
int to,nxt;
N(int t=,int n=):to(t),nxt(n) {}
}ed[maxn<<];
void add(int x,int y){ed[++ct]=N(y,hd[x]); hd[x]=ct;}
void dfs(int x,int f)
{
dep[x]=dep[f]+; siz[x]=; fa[x]=f;
for(int i=hd[x],u;i;i=ed[i].nxt)
{
if((u=ed[i].to)==f)continue;
dfs(u,x); siz[x]+=siz[u];
if(siz[u]>siz[son[x]])son[x]=u;
}
}
void dfs2(int x)
{
dfn[x]=++tim; id[tim]=x;//
if(son[x])top[son[x]]=top[x],dfs2(son[x]);
for(int i=hd[x],u;i;i=ed[i].nxt)
{
if((u=ed[i].to)==fa[x]||u==son[x])continue;
top[u]=u; dfs2(u);
}
}
void pushup(int x){mx[x]=max(mx[x<<],mx[x<<|]);}
void pushdown(int x)
{
if(!lzy[x])return;
lzy[x<<]=lzy[x<<|]=lzy[x];
mx[x<<]=mx[x<<|]=lzy[x];
lzy[x]=;
}
void add(int x,int l,int r,int L,int R,int val)
{
if(l>=L&&r<=R){mx[x]=lzy[x]=val; return;}
pushdown(x);
int mid=((l+r)>>);
if(mid>=L)add(x<<,l,mid,L,R,val);
if(mid<R)add(x<<|,mid+,r,L,R,val);
pushup(x);
}
int ask(int x,int l,int r,int L,int R)
{
if(l>=L&&r<=R)return mx[x];
pushdown(x);
int ret=,mid=((l+r)>>);
if(mid>=L)ret=max(ret,ask(x<<,l,mid,L,R));
if(mid<R)ret=max(ret,ask(x<<|,mid+,r,L,R));
return ret;
}
void update(int x,int y,int val)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
add(,,n,dfn[top[x]],dfn[x],val);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
add(,,n,dfn[y],dfn[x],val);
}
bool query(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
if(ask(,,n,dfn[top[x]],dfn[x])==tot) return ;
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
return (ask(,,n,dfn[y],dfn[x])==tot);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(,); top[]=; dfs2();
for(int i=,a,b,c,d;i<=q;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
update(a,b,++tot);
if(query(c,d))printf("Y\n");
else printf("N\n");
}
return ;
}