带权并查集

一句话理解

带权并查集：边或关系上带差值。

为什么要学

食物链、种类并查集、相对距离。

讲解

fa 之外再维护 d[x] 表示 x 到父（或根）的关系。路径压缩时要更新 d。

例子

x 比 y 大 a，y 比 z 大 b，则可推出 x 比 z 大 a+b。

常见错误

• 压缩路径不更新权。
• 合并时关系方向加反。