带权并查集·直觉

10 分钟

除父亲外再记 d[x],表示 x 到父亲的“关系值”(如距离、差、类别偏移)。find 做路径压缩时,同步累加这条链上的权。它适合“维护相对关系”的问题。

小纸条

带权并查集里除 f[x] 外还需记录什么?

登录 后可看答案

带权并查集·直觉 · 算法进阶 · op599 课程