题目大概说一棵边有方向的树,q个询问,每次询问结点u是否能走到v。

倍增LCA搞即可:

  • 除了par[k][u]表示u结点往上走2k步到达的结点,
  • 再加上upp[k][u]表示u结点往上走2k步经过边的状态:-1表示边都是向下,1表示都是向上,0混合。
  • 这样u、v都往LCA上走就能知道u是否能走到v了。
 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111111 struct Edge{
int v,w,next;
}edge[MAXN<<];
int NE,head[MAXN];
void addEdge(int u,int v,int w){
edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
head[u]=NE++;
} int dep[MAXN],par[][MAXN],upp[][MAXN];
void dfs(int u,int fa){
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
dep[v]=dep[u]+;
par[][v]=u;
upp[][v]=edge[i].w;
dfs(v,u);
}
} void init(int n){
for(int i=; i<; ++i){
for(int j=; j<=n; ++j){
if(par[i-][j]==){
par[i][j]=;
continue;
}
par[i][j]=par[i-][par[i-][j]];
if(upp[i-][j]== && upp[i-][par[i-][j]]==){
upp[i][j]=;
}else if(upp[i-][j]==- && upp[i-][par[i-][j]]==-){
upp[i][j]=-;
}else{
upp[i][j]=;
}
}
}
}
bool lca(int u,int v){
if(dep[u]>dep[v]){
for(int i=; i<; ++i){
if((dep[u]-dep[v])>>i&){
if(upp[i][u]!=) return ;
u=par[i][u];
}
}
if(u==v) return ;
for(int i=; i>=; --i){
if(par[i][u]!=par[i][v]){
if(upp[i][u]!= || upp[i][v]!=-) return ;
u=par[i][u]; v=par[i][v];
}
}
if(upp[][u]!= || upp[][v]!=-) return ;
}else{
for(int i=; i<; ++i){
if((dep[v]-dep[u])>>i&){
if(upp[i][v]!=-) return ;
v=par[i][v];
}
}
if(u==v) return ;
for(int i=; i>=; --i){
if(par[i][u]!=par[i][v]){
if(upp[i][u]!= || upp[i][v]!=-) return ;
u=par[i][u]; v=par[i][v];
}
}
if(upp[][u]!= || upp[][v]!=-) return ;
}
return ;
} int main(){
int n,q,a,b;
while(~scanf("%d",&n)){
NE=;
memset(head,-,sizeof(head));
for(int i=; i<n; ++i){
scanf("%d%d",&a,&b);
addEdge(a,b,-);
addEdge(b,a,);
} dfs(,);
init(n); scanf("%d",&q);
while(q--){
scanf("%d%d",&a,&b);
if(lca(a,b)) puts("Yes");
else puts("No");
}
}
return ;
}

最新文章

  1. 简述HTML DOM及其节点分类
  2. ASP.NET Web API路由系统:路由系统的几个核心类型
  3. java基础总结——开篇
  4. Android Logcat 封装类
  5. linux命令之 用户和群组
  6. 2014 Super Training #4 B Problem Arrangement --状压DP
  7. 桂电在linux环境下使用出校器
  8. hdu.5203.Rikka with wood sticks(数学推导:一条长度为L的线段经分割后可以构成几种三角形)
  9. 【USACO】
  10. Chosen 基本使用
  11. 简单JSONP跨域请求
  12. java面试题(二)
  13. Unix/Linux中的read和write函数
  14. SQL增删改语句
  15. C++的静态联编和动态联编
  16. mysql学习【第4篇】:MySQL函数和编程
  17. 学大数据是先学java还是先学python?
  18. LoveIsIntheAir模板换背景
  19. 【JAVA】什么是冒泡排序?——面试加分题
  20. 【转】Spring学习---Spring IoC容器的核心原理

热门文章

  1. ios cell常用属性
  2. 靶形数独(codevs 1174)
  3. 二、JavaScript语言--JS动画--JS动画效果
  4. yii2.0框架安装心得
  5. MSSQL数据的批量插入
  6. EF环境搭建碰到的问题
  7. saltapi中expr_form参数的使用
  8. WPF QuickStart系列
  9. [译]:Orchard入门——安装Orchard
  10. 批量删除SharePoint 2010的List中的item