Dotcpp  /  题集列表  /  数据结构-倍增求LCA

数据结构-倍增求LCA

题集介绍

数据结构-倍增求LCA

倍增法求最近公共祖先（Lowest Common Ancestor，LCA）是一种用于在树结构中快速解决两个节点的最近公共祖先的算法。它通过预处理和查询的方式实现。

在倍增法中，首先需要对树进行预处理，计算每个节点的第2^k个祖先，其中k为一个正整数。然后，对于任意两个节点u和v，可以通过不断向上跳跃的方式，使得它们距离相等，然后同时向上跳跃，直到找到它们的最近公共祖先。

题集目录

题号 标题 解决/提交
2458 信息学奥赛一本通T1552-点的距离 中等 25/67
2459 信息学奥赛一本通T1553-暗的连锁 中等 4/4
2460 信息学奥赛一本通T1554-异象石 中等 5/6
2461 信息学奥赛一本通T1555-次小生成树 中等 3/8
2462 信息学奥赛一本通T1556-Dis 中等 8/25
2463 信息学奥赛一本通T1557-祖孙询问 中等 34/90
2464 信息学奥赛一本通T1558-聚会 中等 5/11
2465 信息学奥赛一本通T1559-跳跳棋 中等 4/4
  • «
  • ‹
  • 1
  • ›
  • »

题集信息

数据结构-倍增求LCA

创建者 柑普
题目数 8

推荐题集

2017年蓝桥杯第八届省赛及国赛真题


2022年第十三届蓝桥杯大赛软件类省赛Java研究生组真题


2022年第十三届蓝桥杯大赛软件类省赛Python大学B组真题


2022年第十三届蓝桥杯大赛软件类省赛Python大学C组真题


2022年第十三届蓝桥杯大赛软件类决赛C/C++大学A组真题


相关题解

题解2458: 信息学奥赛一本通T1552-点的距离


题解2459: 信息学奥赛一本通T1553-暗的连锁


题解2460: 信息学奥赛一本通T1554-异象石


题解2461: 信息学奥赛一本通T1555-次小生成树


题解2462: 信息学奥赛一本通T1556-Dis


题解2463: 信息学奥赛一本通T1557-祖孙询问


题解2464: 信息学奥赛一本通T1558-聚会


题解2465: 信息学奥赛一本通T1559-跳跳棋