带权重并查集的核心是find与union同步维护相对权重差：weight[i]表示i到父节点的偏移，根节点为0；find路径压缩时累加父节点到根的偏移以更新weight[i]为i到根的直接偏移；union中按约束解出新根偏移并更新总权重。
带权重并查集的核心设计：find 和 union 必须同步维护权重
普通并查集只关心连通性，而带权重的版本必须让每个节点能快速回答“它所属连通分量的总权重是多少”。关键在于：不能在每次查询时遍历整个分量求和——那样退化成 O(n)。正确做法是把权重信息“上推”到根，并在路径压缩时同步更新偏移量。
典型错误是只维护 parent 数组，另用一个全局 map 存根的总权重，结果 union 后忘记更新、或 find 时没修正中间节点的相对权重，导致后续查询错乱。
-
weight[i]表示节点i到其父节点的**相对权重差**（不是绝对值），根节点的weight[root] = 0 -
total_weight[root]单独维护，表示以root为根的连通分量**总权重和**（即所有元素原始权重之和） -
find(i)做路径压缩时，需沿路累加weight并重置为对根的直接偏移 -
union(i, j, w)中的w是“让i所在分量整体相对于j所在分量偏移w”，不是两个根权重相加
C++ 实现中 find 的路径压缩必须重算权重链
标准路径压缩只改 parent[i]，但带权重时，weight[i] 也得从“i→parent[i]→…→root”变成“i→root”。不重算就会丢失中间偏移，后续 find 返回错误相对值。
int find(int x) {
if (parent[x] != x) {
int root = find(parent[x]);
weight[x] += weight[parent[x]]; // 关键：累加父节点到根的偏移
parent[x] = root;
}
return parent[x];
}
注意：这里 weight 是“子到父”的差值，所以递归回溯时累加才得到“子到根”；若定义为“父到子”，符号和累加顺序就得反过来。
立即学习“C++免费学习笔记（深入）”；
- 不能用迭代写法跳过递归回溯，否则无法自然累加路径上的
weight - 如果元素原始权重存在
val[i]数组里，total_weight[root]应在初始化时就设为val[i]，之后只随union改变 - 调用
find(x)后，weight[x]就是x相对于其根的偏移，val[x] + weight[x]不代表什么物理意义——别混淆原始值和相对偏移
union 操作要先 find 再按秩合并，且权重更新不可交换
合并两个连通分量时，目标是让其中一个根的新偏移满足给定约束。例如：要求 i 所在分量整体比 j 所在分量大 w，即 root_i 的总效果 = root_j 的总效果 + w。这需要解出 weight[root_i] 应设为何值。
假设 ri = find(i), rj = find(j)，当前 i 到 ri 偏移是 weight[i]，j 到 rj 是 weight[j]，那么约束等价于：(val[i] + weight[i]) - (val[j] + weight[j]) == w → 但更稳妥的是统一用根视角：
- 令
rj为新根，则需设置weight[ri] = weight[j] - weight[i] + w - 必须保证
ri != rj，否则无意义；且合并后要更新total_weight[rj] += total_weight[ri] - 按秩合并（
rank或size）仍有效，但权重更新公式依赖谁当新根，不能随意交换左右操作数 - 如果用
size合并，记得更新size[rj] += size[ri]；若用rank，只在相等时才增rank[rj]
调试时最容易忽略的三个点
实际写的时候，90% 的 bug 都集中在这三处，而不是逻辑主干：
- 初始化时漏设
weight[i] = 0，尤其当数组用vector<int>(n)</int>默认构造，值为 0 是巧合，显式赋值更安全 -
union前没调用find获取根，直接拿原始输入下标去算weight，导致用的是未压缩路径上的脏数据 - 把“连通分量总权重”和“节点到根的偏移”混为一谈，比如误以为
total_weight[find(x)]是x的当前值——它只是整个集合的原始权重和，与weight[x]无关
权重并查集真正难的不是结构，而是时刻分清“谁相对于谁”“是原始值还是偏移量”“更新发生在哪个节点上”。一旦变量命名模糊（比如叫 dist 而不叫 weight_to_parent），很快就会卡住。
