数据结构-倍增求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-祖孙询问 | 中等题 | 31/86 | |
| 2464 | 信息学奥赛一本通T1558-聚会 | 中等题 | 5/11 | |
| 2465 | 信息学奥赛一本通T1559-跳跳棋 | 中等题 | 4/4 |
前往题解：数据结构-倍增求LCA题解与参考答案
- «
- ‹
- 1
- ›
- »