知识卡片
伪距离沿父链求原树深度
深度维护题允许并查集森林的形状不同于原树。
给每个节点保存伪距离,使从节点到集合根路径的伪距离之和等于该节点在原树中的深度;路径压缩时必须同步修正这些值,具体算法仍待设计。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
The key idea is to maintain in each node v a “pseudodistance” v.d, which is defined so that the sum of the pseudodistances along the simple path from v to the root of its set Si equals the depth of v in Ti.
参考来源
- 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[40000,45000))。
- 结论依据:原文明确伪距离的路径求和不变量,后续实现作为题目提出。
- 原始内容:The key idea is to maintain in each node v a “pseudodistance” v . d , which is defined so that the sum of the pseudodistances along the simple path from v to the root of its set S i equals the depth of v in T i .