首页 > 其他 > 详细

LCA模板

时间:2019-09-02 18:41:37      阅读:76      评论:0      收藏:0      [点我收藏+]

例题 :

https://www.luogu.org/problem/P3379

算法:

首先我们能想出一种暴力算法:先把深度高的点跳到和深度低的点的同一层,然后他们俩一起往上跳,如果两个点相遇了,当前点就是他们的最近公共祖先。但可惜会超时,于是我们考虑一下优化。

优化:

我们可以把跳的过程优化一下,原来是一个一个往上跳,速度太慢,我们就可以用二进制优化一下,2的n次方这样往上跳。已知fa[u][i]表示u的第2的i次方个祖先

LCA模板

原文:https://www.cnblogs.com/qqq1112/p/11448165.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!