热门
最新
红包
立Flag
投票
同城
我的
发布
《浅谈倍增法求解LCA》
考虑一次跳多一点记$fa_{u,k}$表示距离$u$的边数为$2^k$的祖先节点则$fa_{u,k}=fa_{fa_{u,k-1},k-1}$可以通过dfs求出$fa$如果求LCA,我们可以很快让两点来到相同的深度考虑求两点深度差，将差二进制拆分，每次跳一个$2$的幂，时间复杂度$O(\log n)$当然，没必要真的二进制拆分，因为我们要知道是$2$的几次幂，所以用`cmath`的`log2`更加方便这里有一个优化：用$O(n)$的时间复杂度递推求出`log2`的值然后，如果两点深度......
——来自博客 https://blog.csdn.net/DengDuckOI/article/details/125211105
有人想看树上差分吗(单选)
2 人已经参与 已结束
想
0人
不想
1人
钝角
1人
CSDN App 扫码分享
评论
点赞
- 复制链接
- 举报
下一条：
暑期读书计划
