Peterliang

分类

PAT挑战日记(15) 《算法竞赛进阶指南》系列题解(4) 心路历程(1) 未归档(5) 模板(2) 题解(145)

/ 注册

全部文章（共1篇）

树上求LCA两种方法

一、向上标记法比如求x，y的lca，我们先从x向上走到根节点，中途标记每个被走过的点，然后从y向上标记，直到遇到第一个被标记的点就是他们的lca了。(不适用于多次查询操作）时间复杂度：O(n) 二、树上倍增法这种方法主要是利用了倍增的思想，不断地向上试探，同时利用dp不断转移到上面，然后即可求出...

LCA DP

2020-10-05

0 689