洛谷P3398 仓鼠找 sugar 题解

仓鼠找 sugar 题解"/>

洛谷P3398 仓鼠找 sugar 题解

洛谷P3398 仓鼠找 sugar 题解

题目链接：P3398 仓鼠找 sugar

题意：

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

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

n ≤ 1 0 5 , q ≤ 1 0 5 n \le 10^5,q \le 10^5 n≤105,q≤105

简化一下题意，就是给定两个树上的路径判断有没有交集

设 a , b a,b a,b 的LCA为 x x x ， c , d c,d c,d 的LCA为 y y y

不难发现如果两个树有交集，那一定满足以下至少一个条件

• x x x 在 c , d c,d c,d 的路径上
• y y y 在 a , b a,b a,b 的路径上

考虑如何判断是否在路径上

其实很简单，只要 x x x 到 c , d c,d c,d 的距离之和等于 c c c 到 d d d 的距离，则 x x x 就在 c , d c,d c,d 的路径上

同理，只要 y y y 到 a , b a,b a,b 的距离之和等于 a a a 到 b b b 的距离，则 y y y 就在 a , b a,b a,b 的路径上

然后写个倍增LCA就完了

时间复杂度 O ( m log ⁡ n ) O(m \log n) O(mlogn)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)int n,Q,pos=1,head[N],dep[N],lg[N],fa[N][20];
struct Edge{int u,v,next;}e[N<<1];
void addEdge(int u,int v)
{e[++pos]={u,v,head[u]};head[u]=pos;
}
void dfs(int u,int f)
{fa[u][0]=f;dep[u]=dep[f]+1;for(int i=1; i<=lg[dep[u]]; i++)fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=head[u]; i; i=e[i].next)if(e[i].v!=f)dfs(e[i].v,u);
}
int lca(int x,int y)
{if(dep[x]<dep[y]) swap(x,y);while(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];if(x==y) return x;for(int i=lg[dep[x]]; i>=0; i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][0];
}
int dis(int x,int y)
{int d=lca(x,y);return abs(dep[x]-dep[d])+abs(dep[y]-dep[d]);
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// freopen("check.in","r",stdin);// freopen("check.out","w",stdout);cin >> n >> Q;for(int i=1,u,v; i<n; i++){cin >> u >> v;addEdge(u,v);addEdge(v,u);}for(int i=1; i<=n; i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i);dfs(1,1);for(int a,b,c,d; Q--;){cin >> a >> b >> c >> d;int d1=lca(a,b),d2=lca(c,d);if(dis(a,d2)+dis(d2,b)==dis(a,b)||dis(c,d1)+dis(d1,d)==dis(c,d))cout << "Y\n";else cout << "N\n";}return 0;
}