2020-2021:teams:hotpot:200606-200612

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:hotpot:200606-200612 [2020/06/12 16:54]
喝西北风
+++ 2020-2021:teams:hotpot:200606-200612 [2020/06/12 19:37] (当前版本)
lotk
@@ 行 21: / 行 21: @@
 =====本周推荐=====
-林星涵：
+林星涵：「2017 山东二轮集训 Day6」汇合
+[[https://loj.ac/problem/6115|传送门]]
+题目大意：求任意两点的最近公共祖先。
+数据范围：$n$ (点数) $\le$ 900000 $m$（询问） $\le$ 100000 内存限制 4 $Mib$。
+解题思路：乍看之下 $2s$ 时限，$900000$ 的点数，可以用爬树法水过，但是由于内存限制感人，显然 $nlogn$ 的空间是会 $MLE$的。因此，这题我们需要采用树上分块的思想，用块来统计信息爬树。只需处理好每一块深度最浅的点，每一块的上一块的编号，每一块在由块组成的这个新树中的深度等信息，别的操作基本上都与爬树法相同。
 陶吟翔：[FJOI2014]树的重心

2020-2021/teams/hotpot/200606-200612.1591952074.txt.gz · 最后更改: 2020/06/12 16:54 由喝西北风