2020-2021:teams:hotpot:lca
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:lca [2020/07/16 14:55] misakatao 更新 |
2020-2021:teams:hotpot:lca [2020/07/22 13:39] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 53: | 行 53: | ||
| ======树链剖分求LCA====== | ======树链剖分求LCA====== | ||
| - | (留在树链剖分部分再写，到时候给链接) | + | [[treechain|树链剖分]] |
| ======RMQ算法求LCA====== | ======RMQ算法求LCA====== | ||
| - | ======例题——BZOJ1001狼抓兔子====== | + | RMQ算法本来是在一维数组上求最大最小值的算法，方法与倍增基本一致，令$f[i][j]$表示从$i$向右长度为$2^j$的位置内的最大/最小值，递推方式也与倍增算法一直。 |
| - | =====题目大意===== | + | 那么如何利用RMQ算法求解LCA呢，我们对要求的树首先进行dfs，然后得到每一个点的dfs序，之后我们每次经过这个点，就把这个点放入一个序列的最后，这个序列被称为欧拉序，然后在查询$LCA(x,y)$时，我们首先找到$x$和$y$的dfs序，找到两个dfs序最先出现的位置，那么在欧拉序这两个位置之间dfs序最小的点就是它们的LCA。这一做法还可以进一步优化使得代码难度降低。 |
| - | =====解题思路===== | ||
| - | |||
| - | =====代码实现===== | ||
2020-2021/teams/hotpot/lca.1594882544.txt.gz · 最后更改: 2020/07/16 14:55 由 misakatao
