2020-2021:teams:hotpot:200606-200612
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200606-200612 [2020/06/12 19:36] lotk |
2020-2021:teams:hotpot:200606-200612 [2020/06/12 19:37] (当前版本) lotk |
||
|---|---|---|---|
| 行 27: | 行 27: | ||
| 题目大意：求任意两点的最近公共祖先。 | 题目大意：求任意两点的最近公共祖先。 | ||
| - | 数据范围：n (点数) /le 900000 m（询问） /le 100000 内存限制 4 Mib。 | + | 数据范围：$n$ (点数) $\le$ 900000 $m$（询问） $\le$ 100000 内存限制 4 $Mib$。 |
| - | 解题思路：乍看之下 2s 时限， 900000的点数，可以用爬树法水过，但是由于内存限制感人，显然 &nlogn& 的空间是会MLE的。因此，这题我们需要采用树上分块的思想，用块来统计信息爬树。只需处理好每一块深度最浅的点，每一块的上一块的编号，每一块在由块组成的这个新树中的深度等信息，别的操作基本上都与爬树法相同。 | + | 解题思路：乍看之下 $2s$ 时限，$900000$ 的点数，可以用爬树法水过，但是由于内存限制感人，显然 $nlogn$ 的空间是会 $MLE$的。因此，这题我们需要采用树上分块的思想，用块来统计信息爬树。只需处理好每一块深度最浅的点，每一块的上一块的编号，每一块在由块组成的这个新树中的深度等信息，别的操作基本上都与爬树法相同。 |
| 陶吟翔：[FJOI2014]树的重心 | 陶吟翔：[FJOI2014]树的重心 | ||
2020-2021/teams/hotpot/200606-200612.1591961764.txt.gz · 最后更改: 2020/06/12 19:36 由 lotk
