题解 P3398 【仓鼠找sugar】

· · 题解

这个题正解的思路不是特别好想，但我们还是可以考虑暴力的。

直接暴力地把x到y这条路径上的所有点标记一下，然后查询a到b的路径上是否有被标记的点即可。

考虑怎么标记呢？

emmm......

树上区间修改......

树剖啊！（不会LCT）

看到题解里也有使用这种思路的，但还是发一波，主要是因为我这个用到了位元算加速，没有必要使用区间加法，区间和这种操作。直接或运算就好了。

还有个可以优化的地方就是在查询的时候如果发现已经找到一个标记，不用继续找了，直接退出即可。

代码如下

#include<iostream>
#include<cctype>
#include<cstdio>
#include<algorithm>
#define N 220000
#define inf 9999999999
#define ll long long
using namespace std;
inline ll read()
{
    ll x=0,flag=1;
    char ch=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
    while(isdigit(ch)) {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*flag;
}
struct edge
{
    ll to;
    ll next;
}e[N];
ll num,head[N];
inline void add(ll x,ll y)
{
    num++;
    e[num].to=y;
    e[num].next=head[x];
    head[x]=num;
}
ll n,m,fa[N],dep[N],sz[N],son[N],top[N];
void first_dfs(ll x,ll t)
{
    sz[x]++;
    dep[x]=t;
    for(ll i=head[x];i;i=e[i].next)
    {
        ll to=e[i].to;
        if(!dep[to])
        {
            first_dfs(to,t+1);
            fa[to]=x;
            if(sz[to]>sz[son[x]])
            son[x]=to;
            sz[x]+=sz[to];
        }
    } 
}
ll times,id[N];
void second_dfs(ll x,ll tp)
{
    times++;
    id[x]=times;
    top[x]=tp; 
    if(son[x])
    second_dfs(son[x],tp);
    for(ll i=head[x];i;i=e[i].next)
    {
        ll to=e[i].to;
        if(!id[to])
            second_dfs(to,to);
    } 
}
struct Segment_Tree
{
    #define lson o<<1
    #define rson o<<1|1
    #define mid ((l+r)>>1)
    ll flagv[N<<2],setv[N<<2];
    inline void pushup(ll o)
    {
        flagv[o]=flagv[lson]|flagv[rson];
    }
    inline void pushdown(ll o)
    {
        if(setv[o]!=-1)
        {
            flagv[lson]=flagv[rson]=setv[lson]=setv[rson]=setv[o];
            setv[o]=-1;
        }
    }
    void build(ll o,ll l,ll r)
    {
        setv[o]=-1;
        if(l==r)
            return;
        build(lson,l,mid);
        build(rson,mid+1,r);
    }
    ll query(ll o,ll l,ll r,ll ql,ll qr)
    {
        pushdown(o);
        if(ql<=l&&r<=qr)
        return flagv[o];
        ll ans=0;
        if(ql<=mid)ans=ans|query(lson,l,mid,ql,qr);
        if(ans)return ans;
        if(qr>mid)ans=ans|query(rson,mid+1,r,ql,qr);
        return ans;
    }
    void optset(ll o,ll l,ll r,ll ql,ll qr,ll num)
    {
        pushdown(o);
        if(ql<=l&&r<=qr)
        {
            flagv[o]=setv[o]=num;
            return;
        }
        if(ql<=mid)optset(lson,l,mid,ql,qr,num);
        if(qr>mid)optset(rson,mid+1,r,ql,qr,num);
        pushup(o);
    }
}T;
ll qrange(ll x,ll y)
{
    ll ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        swap(x,y);
        ans=ans|T.query(1,1,n,id[top[x]],id[x]);
        if(ans)return ans;
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])
    swap(x,y);
    ans=ans|T.query(1,1,n,id[y],id[x]);
    return ans;
}
ll optrange(ll x,ll y,ll cnt)
{
    ll ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        swap(x,y);
        T.optset(1,1,n,id[top[x]],id[x],cnt);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])
    swap(x,y);
    T.optset(1,1,n,id[y],id[x],cnt);
    return ans;
}
int main()
{
    ll i,x,y,x1,x2,y1,y2;
    n=read();
    m=read();
    for(i=1;i<=n-1;i++)
    {
        x=read();
        y=read();
        add(x,y);
        add(y,x);
    }
    fa[1]=1;
    first_dfs(1,1);
    second_dfs(1,1);
    T.build(1,1,n);
    for(i=1;i<=m;i++)
    {
        x1=read();
        y1=read();
        x2=read();
        y2=read();
        optrange(x2,y2,1);
        ll ans=qrange(x1,y1);
        if(ans)
        printf("Y\n");
        else
        printf("N\n");
        optrange(x2,y2,0);
    }
    return 0;
}