题目链接:

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 ;
}

最新文章

  1. C++静态库与动态库
  2. Memcache及telnent命令详解
  3. Main()
  4. cordova添加platform
  5. 当EL遇到char
  6. UESTC 2016 Summer Training #6 Div.2
  7. 005. asp.net页面常用指令
  8. [iOS Animation]-CALayer 图层性能
  9. kettle-数据源配置化-开发、生产采用不同配置
  10. 04_VMware虚拟机网络配置
  11. Matplotlib快速入门笔记
  12. 使用domain模块捕获异步回调中的异常
  13. 十大豪门推送sdk,哪个更适合你
  14. Hadoop 数据排序(一)
  15. Dll的编写 在unity中加载
  16. Openrasp源码分析
  17. 分布式强化学习基础概念(Distributional RL )
  18. JMeter接口&amp;性能测试
  19. LeetCode——Contains Duplicate II
  20. 20165324_mybash

热门文章

  1. Java-SpringCloud:目录
  2. tabBar的图标不被系统渲染
  3. 前后端分离之接口登陆权限token
  4. MVC中添加模块区域,并设置RedirectToAction跳转
  5. vue中采用axios发送请求及拦截器
  6. 移除HTML5 input在type=&quot;search&quot;时的清除按钮
  7. C#中SQL参数传入空值报错解决方案
  8. C++ 简单内存泄漏检测方法
  9. iOS的流畅性
  10. iOS9 &amp; Xcode7 下设置LaunchImage启动图片 问题及解决