[JZOJ 5852] [NOIP2018提高组模拟9.6] 相交 解题报告 (倍增+LCA)
2024-08-29 21:39:25
题目链接:
http://172.16.0.132/senior/#main/show/5852
题目:
题目大意:
多组询问,每次询问树上两条链是否相交
题解:
两条链相交并且仅当某一条链的两个端点的LCA在另一个端点上
对于每次询问,我们分别处理出两条链端点的LCA,通过倍增判断是否存在一条链的LCA在另一条链上
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std; const int N=1e5+;
int n,tot;
int h[N],fa[N][],dep[N];
struct E{
int to,nxt;
}e[N<<];
inline int read(){
char ch=getchar();int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
void link(int u,int v){e[++tot]=(E){v,h[u]};h[u]=tot;}
void dfs(int x,int pre){
for (int i=;i<;i++) fa[x][i]=fa[fa[x][i-]][i-];
for (int i=h[x],y;i;i=e[i].nxt){
if ((y=e[i].to)==pre) continue;
fa[y][]=x;dep[y]=dep[x]+;
dfs(y,x);
}
}
int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
for (int i=;i>=;i--) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if (x==y) return x;
for (int i=;i>=;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][];
}
bool chk(int a,int b,int La,int Lb){
if (dep[Lb]<dep[La]) return ;
if (dep[a]>=dep[Lb]){
for (int i=;i>=;i--) if (dep[fa[a][i]]>=dep[Lb]&&dep[fa[a][i]]>=dep[La]) a=fa[a][i];
if (a==Lb) return ;
}
if (dep[b]>=dep[Lb]){
for (int i=;i>=;i--) if (dep[fa[b][i]]>=dep[Lb]&&dep[fa[b][i]]>=dep[La]) b=fa[b][i];
if (b==Lb) return ;
}
return ;
}
int main(){
freopen("inter.in","r",stdin);
freopen("inter.out","w",stdout);
n=read();
for (int i=,u,v;i<n;i++){
u=read();v=read();
link(u,v);link(v,u);
}
dep[]=;dfs(,);
int q=read();
while (q--){
int a=read(),b=read(),c=read(),d=read();
int lab=lca(a,b),lcd=lca(c,d);
//printf("%d %d\n",lab,lcd);
if (chk(a,b,lab,lcd)||chk(c,d,lcd,lab)) puts("YES");
else puts("NO");
}
return ;
}
最新文章
- C++静态库与动态库
- Memcache及telnent命令详解
- Main()
- cordova添加platform
- 当EL遇到char
- UESTC 2016 Summer Training #6 Div.2
- 005. asp.net页面常用指令
- [iOS Animation]-CALayer 图层性能
- kettle-数据源配置化-开发、生产采用不同配置
- 04_VMware虚拟机网络配置
- Matplotlib快速入门笔记
- 使用domain模块捕获异步回调中的异常
- 十大豪门推送sdk,哪个更适合你
- Hadoop 数据排序(一)
- Dll的编写 在unity中加载
- Openrasp源码分析
- 分布式强化学习基础概念(Distributional RL )
- JMeter接口&;性能测试
- LeetCode——Contains Duplicate II
- 20165324_mybash