最近公共祖先(LCA)

 

祖孙询问

给定一棵包含 n 个节点的有根无向树,节点编号互不相同,但不一定是 1∼n。

有 m 个询问,每个询问给出了一对节点的编号 x 和 y,询问 x 与 y 的祖孙关系。

输入格式

输入第一行包括一个整数 表示节点个数;

接下来 n 行每行一对整数 a 和 b,表示 a和 b 之间有一条无向边。如果 b是 −1,那么 a 就是树的根;

第 n+2 行是一个整数 m 表示询问个数;

接下来 m 行,每行两个不同的正整数 x 和 y,表示一个询问。

输出格式

对于每一个询问,若 x 是 y 的祖先则输出 1,若 y 是 x 的祖先则输出 2,否则输出 0。

数据范围

1≤n,m≤4×10^4
1≤每个节点的编号≤4×10^4

输入样例:

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

输出样例:

1
0
0
0
2

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=4e4+10,M=2*N;
int h[N],e[M],ne[M],idx;
int fa[N][16];
int depth[N];
int n,m;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0;//哨兵
    depth[root]=1;//根节点深度为1
    queue<int>q;
    q.push(root);
    //宽搜
    while(q.size())
    {
        int t=q.front();
        q.pop();
        //遍历下一层
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            //此时还没有更新
            if(depth[j]>depth[t]+1)//depth[j]==0x3f3f3f3f
            {
                //深度加一
                depth[j]=depth[t]+1;
                q.push(j);
                //跳一层是j的父节点 2^0
                fa[j][0]=t;
                 /*
                i  →  mid  →  t
                  2^j-1  2^j-1
                  f[i][j-1] f[i][j]
                mid = f[i][j-1]  
                t = f[i][j]
                则f[i][j] = f[mid][j-1] = f[f[i][j-1]][j-1]
                */
                for(int k=1;k<=15;k++)
                {
                    fa[j][k]=fa[fa[j][k-1]][k-1];
                }
                 /*
                举个例子理解超过根节点是怎么超过的
                因为我们没有对根节点fa[1][0]赋值,那么fa[1][0] = 0;
                    1
                   / \
                  2   3 
                fa[1][0] = 0;
                fa[2][0] = 1;
                fa[2][1] = fa[fa[2][0]][0] = fa[1][0] = 0;
                */
            }
        }
    }
}
int lca(int a,int b)
{
     // 为方便处理 当a在b上面时 把a b 互换 
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=15;k>=0;k--)
    {
        //当a跳完2^k依然在b下面 我们就一直跳
        //二进制拼凑法 
        if(depth[fa[a][k]]>depth[b])
        {
            //更新跳
            a=fa[a][k];
        }
    }
    //如果跳到了b 判断一下 是否跳到了b
    if(a==b) return a;
    for(int k=15;k>=0;k--)
    {
     // 假如a,b都跳出根节点,fa[a][k]==fa[b][k]==0 不符合更新条件
        if(fa[a][k]!=fa[a][k])
        {
            a=fa[a][k];
            b=fa[a][k];
        }
    }
    //循环结束 到达lca下一层
    //lca(a,b) = 再往上跳1步即可
    return fa[a][0];
}
int main()
{
    cin>>n;
    //初始化头节点
    memset(h,-1,sizeof h);
    int root=0;
    while(n--)
    {
        //建图
        int a,b;cin>>a>>b;
        if(b==-1) root=a;
        else 
        {
            add(a,b);
            add(b,a);
        }
    }
    //建depth[N] fa[N][15]
    bfs(root);
    cin>>m;
    while(m--)
    {
        int a,b;cin>>a>>b;
        int num=lca(a,b);
        if(num==a) cout<<"1"<<endl;
        else if(num==b) cout<<"2"<<endl;
        else cout<<"0"<<endl;
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/484359.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于YOLOv8深度学习的橙子病害智能诊断与防治系统【python源码+Pyqt5界面+数据集+训练代码】深度学习实战、目标分类

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…

【MySQL】复合查询——基本单表查询、多表查询、自连接、子查询、使用from进行子查询、合并查询

文章目录 MySQL复合查询1. 基本单表查询2. 多表查询3. 自连接4. 子查询4.1 单行子查询4.2 多行子查询4.3 多列子查询4.4 使用from进行子查询 5. 合并查询5.1 union5.2 union all MySQL 复合查询 数据库的复合查询是指在一个查询中结合使用多个查询条件或查询子句&#xff0c;以…

java多线程编程面试题总结

一些最基本的基础知识就不总结了&#xff0c;参考之前写的如下几篇博客&#xff0c;阅读顺序从上到下&#xff0c;依次递进。 java 多线程 多线程概述及其三种创建方式 线程的常用方法 java 线程安全问题 三种线程同步方案 线程通信&#xff08;了解&#xff09; java 线程池…

CSS案例-2.简单版侧边栏练习

效果 知识点 标签显示模式 块级元素 block-level 常见元素:<h1>~<h6>、<p>、<div>、<ul>、<ol>、<li>等。 特点: 独占一行长度、宽度、边距都可以控制宽度默认是容器(父级宽度)的100%是一个容器及盒子,里面可以放行内或者…

spring注解驱动系列--AOP探究二

上篇中记录了AnnotationAwareAspectJAutoProxyCreator的创建以及注册&#xff0c;主要是 1、EnableAspectJAutoProxy 注解会开启AOP功能 2、然后这个注解会往容器中注册一个AnnotationAwareAspectJAutoProxyCreator组件。 3、之后在容器创建过程中&#xff0c;注册后置处理器&a…

【免费】【随机优化】智能配电网的双时间尺度随机优化调度

目录 1 主要内容 2 部分代码 3 部分程序结果 4 下载链接 1 主要内容 该程序为文章《Two-Timescale Stochastic Dispatch of Smart Distribution Grids》的源代码&#xff0c;主要做的是主动配电网的双时间尺度随机优化调度&#xff0c;该模型考虑配电网的高效和安全运行涉及…

【大模型】在VS Code(Visual Studio Code)上安装中文汉化版插件

文章目录 一、下载安装二、配置显示语言&#xff08;一&#xff09;调出即将输入命令的搜索模式&#xff08;二&#xff09;在大于号后面输入&#xff1a;Configure Display Language&#xff08;三&#xff09;重启 三、总结 【运行系统】win 11 【本文解决的问题】 1、英文不…

【JS】如何避免输入中文拼音时触发input事件

现有一段代码&#xff0c;监听input事件。 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" con…

GDC期间LayaAir启动全球化战略

3 月 18 日至 3 月 22 日&#xff0c;一年一度的游戏开发者大会&#xff08;GDC&#xff09;在美国旧金山举行。在此期间&#xff0c;Layabox宣布LayaAir引擎启动全球扩张战略&#xff0c;这标志着引擎将步入快速发展的新阶段。此举旨在利用公司先进的3D引擎技术&#xff0c;将…

mysql体系结构及主要文件

目录 1.mysql体系结构 2.数据库与数据库实例 3.物理存储结构​编辑 4.mysql主要文件 4.1数据库配置文件 4.2错误日志 4.3表结构定义文件 4.4慢查询日志 4.4.1慢查询相关参数 4.4.2慢查询参数默认值 4.4.3my.cnf中设置慢查询参数 4.4.4slow_query_log参数 4.4.…

B端设计:如何让UI组件库成为助力,而不是阻力。

首发2023-09-24 15:42贝格前端工场 Hi&#xff0c;我是大千UI工场&#xff0c;网上的UI组件库琳琅满目&#xff0c;比如elementUI、antdesign、iview等等&#xff0c;甚至很多前端框架&#xff0c;也出了很多UI组件&#xff0c;如若依、Layui、bootstrap等等&#xff0c;作为U…

01.数据归档工具的选择-Percona Toolkit,并centos7.9中安装

1.需求 1.1.在实际的业务使用过程中&#xff0c;我们既要考虑服务器硬件的成本&#xff0c;也要考虑系统的稳定性。所以就有了数据归档的这个业务需求了。我们需要把一些老的数据&#xff0c;比如两年前的数据移出去。增强数据库的性能。 1.2.在进行数据归档的过程中&#xf…

【云开发笔记No.6】腾讯CODING平台

腾讯云很酷的一个应用&#xff0c;现在对于研发一体化&#xff0c;全流程管理&#xff0c;各种工具层出不穷。 云时代用云原生&#xff0c;再加上AI&#xff0c;编码方式真是发生了质的变化。 从前&#xff0c;一个人可以写一个很酷的软件&#xff0c;后来&#xff0c;这变得…

RDGCN翻译

RDGCN翻译 Relation-Aware Entity Alignment for Heterogeneous Knowledge Graphs 面向异质知识图谱的关系感知实体对齐 阅读时间&#xff1a;2024.03.24 领域&#xff1a;知识图谱&#xff0c;知识对齐 作者&#xff1a;Yuting Wu等人 PKU 出处&#xff1a;IJCAI Abstract…

蓝桥杯 2023 省A 颜色平衡树

树上启发式合并是一个巧妙的方法。 dsu on tree&#xff0c;可以称为树上启发式合并&#xff0c;是一种巧妙的暴力。用一个全局数组存储结果&#xff0c;对于每棵子树&#xff0c;有以下操作&#xff1a; 先遍历轻儿子&#xff0c;处理完轻儿子后将数组清零&#xff08;要再…

小目标检测篇 | YOLOv8改进之增加小目标检测层(针对Neck网络为AFPN)

前言:Hello大家好,我是小哥谈。小目标检测是计算机视觉领域中的一个研究方向,旨在从图像或视频中准确地检测和定位尺寸较小的目标物体。相比于常规目标检测任务,小目标检测更具挑战性,因为小目标通常具有低分辨率、低对比度和模糊等特点,容易被背景干扰或遮挡。本篇文章就…

stm32启动文件里面的__main和主函数main()

一、__main和main()之间的关系 先来对stm32启动过程简单学习 启动文件里面的Reset_Handler&#xff1a; 调用过程&#xff1a; stm32在启动后先进入重启中断函数Reset_Handler&#xff0c;其中会先后调用SystemInit和__main函数&#xff0c; __main函数属于c库函数&…

[Java基础揉碎]final关键字

目录 介绍 在某些情况下&#xff0c;程序员可能有以下需求&#xff0c;就会使用到final final注意事项和讨论细节 1) final修饰的属性又叫常量&#xff0c;一般用XX_XX_XX来命名 2) final修饰的属性在定义时&#xff0c;必须赋初值&#xff0c;并且以后不能再修改&#…

chatgpt和 github copilot chat哪个更强

chatgpt大家应该都不陌生 ChatGPT 是由 OpenAI 开发的一种基于 GPT&#xff08;生成式预训练模型&#xff09;的聊天机器人。它可以生成语言上下文相关的响应&#xff0c;从而进行自然语言对话。ChatGPT 利用大规模的语言数据进行预训练&#xff0c;并通过微调或在线学习来适应…

【】(综合练习)博客系统

在之前的学些中&#xff0c;我们掌握了Spring框架和MyBatis的基本使用&#xff0c;接下来 我们就要结合之前我们所学的知识&#xff0c;做出一个项目出来 1.前期准备 当我们接触到一个项目时&#xff0c;我们需要对其作出准备&#xff0c;那么正规的准备是怎么样的呢 1.了解需求…