[LUOGU3398]仓鼠找sugar

题目

题目描述

小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？

小仓鼠那么弱，还要天天被zzq大爷虐，请你快来救救他吧！

输入输出格式

输入格式：

第一行两个正整数n和q，表示这棵树节点的个数和询问的个数。

接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。

接下来q行，每行四个正整数a、b、c和d，表示节点编号，也就是一次询问，其意义如上。

输出格式：

对于每个询问，如果有公共点，输出大写字母“Y”；否则输出“N”。

输入输出样例

输入样例#1：

输出样例#1：

Y
N
Y
Y
Y

说明

20%的数据 n<=200,q<=200

40%的数据 n<=2000,q<=2000

70%的数据 n<=50000,q<=50000

100%的数据 n<=100000,q<=100000

题解

很蒟的我用的树剖…先修改仓鼠走过的路径

做个标记，在查询基友走过的路径上是否有标记

开始我用bool标记路径，每次询问就$memset$清空QAQ

然后超时了~~竟然还有40分~~

于是用int标记，每次询问加$1$

维护区间最大值，最后看是否相等就行了

代码

# include<iostream>
# include<cstdio>
# include<cstring>
# include<queue>
#define mid (l+r>>1)
#define tl (k<<1)
#define tr (k<<1|1)
#define ini inline int
#define inv inline void
using namespace std;
const int MAX=1e5+1;
struct p{
    int lazy,use;
}s[MAX<<2];
struct q{
    int x,y;
}c[MAX<<1];
int n,m,num,cnt,tot;
int h[MAX],d[MAX],son[MAX],top[MAX],fa[MAX],id[MAX],siz[MAX];
ini read()
{
    int x=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch))
    {
        x=x*10+ch-48;
        ch=getchar();
    }
    return x;
}
inv add(int x,int y)
{
    c[++num].x=h[x];
    c[num].y=y;
    h[x]=num;
}
void dfs(int x,int f)
{
    fa[x]=f;
    d[x]=d[f]+1;
    siz[x]=1;
    for(int i=h[x];i;i=c[i].x)
      {
          int y=c[i].y;
          if(y==f) continue;
          dfs(y,x);
          siz[x]+=siz[y];
          if(siz[son[x]]<siz[y])
          son[x]=y;
      }
}
void dfs1(int x,int tp)
{
    top[x]=tp;
    id[x]=++cnt;
    if(son[x]) dfs1(son[x],tp);
    for(int i=h[x];i;i=c[i].x)
      {
          int y=c[i].y;
          if(y==fa[x]||y==son[x])
          continue;
          dfs1(y,y);
      }
}
inv pus(int k)
{
    s[k].use=max(s[tl].use,s[tr].use);
}
inv down(int k)
{
    int f=s[k].lazy;
    s[tl].lazy=s[tr].lazy=f;
    s[tl].use=s[tr].use=f;
    s[k].lazy=0;
}
void change(int l,int r,int k,int L,int R,int dis)
{
    if(l>R||r<L) return;
    if(l>=L&&r<=R)
    {
        s[k].lazy=s[k].use=dis;
        return;
    }
    if(s[k].lazy) down(k);
    change(l,mid,tl,L,R,dis);
    change(mid+1,r,tr,L,R,dis);
    pus(k);
}
inv CHANGE(int x,int y,int dis)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        change(1,n,1,id[top[x]],id[x],dis);
        x=fa[top[x]];
    }
    if(d[x]>d[y]) swap(x,y);
    change(1,n,1,id[x],id[y],dis);
}
int ask(int l,int r,int k,int L,int R)
{
    if(l>R||r<L) return 0;
    if(l>=L&&r<=R)
    return s[k].use;
    if(s[k].lazy) down(k);
    return max(ask(l,mid,tl,L,R),ask(mid+1,r,tr,L,R));
}
char ASK(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        if(ask(1,n,1,id[top[x]],id[x])==tot) return 'Y';
        x=fa[top[x]];
    }
    if(d[x]>d[y]) swap(x,y);
    if(ask(1,n,1,id[x],id[y])==tot) return 'Y';
    return 'N';
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<n;i++)
      {
          int x=read(),y=read();
          add(x,y),add(y,x);
      }
    dfs(1,0);
    dfs1(1,1);
    for(int i=1;i<=m;i++)
      {
          int a1=read(),b1=read(),a2=read(),b2=read();
        CHANGE(a1,b1,++tot);
        printf("%c\n",ASK(a2,b2));
      }
    return 0;
}

题目