首页 > 分享 > 【Luogu3398】仓鼠找sugar（树链剖分）

【Luogu3398】仓鼠找sugar（树链剖分）

萌宠菠菠乐园
2025-01-06 21:52

题面

题目描述

小仓鼠的和他的基（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：
5 5
2 5
4 2
1 3
1 4
5 1 5 1
2 2 1 4
4 1 3 4
3 1 1 5
3 5 1 4
输出样例#1：
Y
N
Y
Y
Y

题解

比较简单吧。。。
懒得多想了
每次的两条路径，一次修改，一次查询
修改就把第一条路径上面的点全部搞一下（比如记录一下当前是第几组询问）
然后再检查一下第二条路径上是否存在标记即可

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; #define MAX 101000 #define lson (now<<1) #define rson (now<<1|1) struct Line { int v,next; }e[MAX<<1]; int h[MAX],cnt=1; inline void Add(int u,int v) { e[cnt]=(Line){v,h[u]}; h[u]=cnt++; } inline int read() { int x=0,t=1;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t; } struct Node { int v; int l; }t[MAX<<2]; int fa[MAX],size[MAX],hson[MAX],dep[MAX],dfn[MAX],tim; int top[MAX],low[MAX],n,L,R,W; void dfs1(int u,int ff) { fa[u]=ff;size[u]=1;dep[u]=dep[ff]+1; for(int i=h[u];i;i=e[i].next) { int v=e[i].v; if(v==ff)continue; dfs1(v,u); size[u]+=size[v]; if(size[v]>size[hson[u]])hson[u]=v; } } void dfs2(int u,int tp) { top[u]=tp;dfn[u]=++tim; if(hson[u])dfs2(hson[u],tp); for(int i=h[u];i;i=e[i].next) { int v=e[i].v; if(v==hson[u]||v==fa[u])continue; dfs2(v,v); } low[u]=tim; } void putlazy(int now,int w) { t[now].v=t[now].l=w; } void pushdown(int now) { if(!t[now].l)return; t[lson].v=t[rson].v=t[now].l; t[lson].l=t[rson].l=t[now].l; t[now].l=0; } void Modify(int now,int l,int r) { if(l>=L&&r<=R){putlazy(now,W);return;} pushdown(now); int mid=(l+r)>>1; if(R>mid)Modify(rson,mid+1,r); if(L<=mid)Modify(lson,l,mid); t[now].v=max(t[lson].v,t[rson].v); } int Query(int now,int l,int r) { if(l>=L&&r<=R){return t[now].v;} pushdown(now); int mid=(l+r)>>1; int ret=0; if(R>mid)ret=max(ret,Query(rson,mid+1,r)); if(L<=mid)ret=max(ret,Query(lson,l,mid)); return ret; } void jump1(int u,int v) { while(top[u]!=top[v]) { if(dep[top[u]]<dep[top[v]])swap(u,v); L=dfn[top[u]],R=dfn[u]; Modify(1,1,n); u=fa[top[u]]; } if(dep[u]<dep[v])swap(u,v); L=dfn[v],R=dfn[u]; Modify(1,1,n); } int jump2(int u,int v) { int ret=0; while(top[u]!=top[v]) { if(dep[top[u]]<dep[top[v]])swap(u,v); L=dfn[top[u]],R=dfn[u]; ret=max(ret,Query(1,1,n)); u=fa[top[u]]; } if(dep[u]<dep[v])swap(u,v); L=dfn[v],R=dfn[u]; ret=max(ret,Query(1,1,n)); return ret; } int main() { n=read();int Q=read(); for(int i=1;i<n;++i) { int u=read(),v=read(); Add(u,v);Add(v,u); } dfs1(1,0);dfs2(1,1); while(Q--) { int u=read(),v=read();W++; jump1(u,v); u=read(),v=read(); jump2(u,v)==W?puts("Y"):puts("N"); } return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141