2020-2021:teams:legal_string:jxm2001:other:错题集_2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/09 00:15] jxm2001 |
2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/09 00:16] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| 考虑倒序枚举每个最小距离，求出该最小距离至少需要的关键点个数，然后更新该关键点个数对应的答案。 | 考虑倒序枚举每个最小距离，求出该最小距离至少需要的关键点个数，然后更新该关键点个数对应的答案。 | ||
| - | 总操作数为 $O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$，删除子树和查询祖先操作时间复杂度为 $O(\log n)$，于是总时间复杂度为 $O\left(n\log^2 n\right)$。 | + | 总操作数为 $O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$，删除子树和查询祖先操作时间复杂度为 $O(\log n)$。 |
| + | |||
| + | 于是总时间复杂度为 $O\left(n\log^2 n\right)$。 | ||
| 注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。 | 注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。 | ||
2020-2021/teams/legal_string/jxm2001/other/错题集_2.1596903337.txt.gz · 最后更改: 2020/08/09 00:15 由 jxm2001
